这题赛场上过了一百多人，然而我们一点思路都没有，并不是我们实力不够，而是之前总是逃避DP，，于是就放过了这么一个简单的DP题。
题意：给一个长度为n的数组，找出其中长度为m的递增子序列的个数，答案对10^9+7取余。
样例输入
2
3 2
1 2 3
3 2
3 2 1
样例输出
3
0
这题乍一看，第一感觉是一个DP加上组合数学的题目，那么既然是DP就要找到状态转移方程，最难的莫过于想到开这样一个数组dp[i][j]表示以第i个数结尾，长度为j的递增子序列的个数，其实如果想到这一步，离成功也不远了，同时我们可以否定一开始的判断，这题里面并没有组合数学。
当我们试图把第i个数放入子序列中形成以第i个数结尾，长度为j的递增子序列，便需要遍历所有以k(1~i-1)结尾的长度为j-1的，并且a[k]<a[i]的子序列的个数，并全部累加在dp[i][j]上。
代码如下：
/* * test.cpp * * Created on: 2015-10-21 *Author: Ivan_w */#include<iostream>#include<stdio.h>#include<string.h>#include<math.h>#include<algorithm>#include<stdlib.h>#include<queue>#include<stack>#include<map>#include<vector>#define mem(a) memset(a,0,sizeof(a))#define pfn printf("\n")#define ll __int64#define pfd(a) printf("%d\n",a)#define pf2d(a,b) printf("%d %d\n",a,b)#define pf3d(a,b,c) printf("%d %d %d\n",a,b,c)#define pfs(a) printf("%s\n",a)#define sfd(a) scanf("%d",&a)#define sf2d(a,b) scanf("%d%d",&a,&b)#define sf3d(a,b,c) scanf("%d%d%d",&a,&b,&c)#define sfs(a) scanf("%s",a)#define sfscanf#define pfprintf#define fr(i,n) for(int i=0;i<n;i++)#define wang int#define bo main#define byebye return 0#define bye returnconst double PI = acos(-1.0);const double e = exp(1.0);template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }template<class T> inline T Min(T a, T b) { return a < b ? a : b; }template<class T> inline T Max(T a, T b) { return a > b ? a : b; }bool cmpbig(int a,int b){return a>b;}bool cmpsmall(int a,int b){return a<b;}using namespace std;#define N 1000+10#define MOD 100000007int a[N];int dp[N][N];wang bo(){//freopen("1.txt","w",stdout);freopen("1.txt","r",stdin);//freopen("2.txt","w",stdout);int t;while(~sfd(t)){for(int cas=1;cas<=t;cas++){printf("Case #%d: ",cas);int n,m;sf2d(n,m);for(int i=1;i<=n;i++){sfd(a[i]);}mem(dp);for(int i=1;i<=n;i++)//结尾为i{dp[i][1]=1;for(int j=2;j<=m;j++)//长度为j{for(int k=1;k<i;k++){if(a[k]<a[i])dp[i][j]+=dp[k][j-1];dp[i][j]%=MOD;}}}int ans=0;for(int i=1;i<=n;i++){ans+=dp[i][m];ans%=MOD;}pfd(ans);}}byebye;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
福报够的人，从来就没听到过是非。
