UP UP UP!(dp)

UP UP UP!

Time Limit: 1 Sec Memory Limit: 128 MB Submit: 92 Solved: 27
Submit Status Web Board

Description

题意很简单，给你长度为n的序列，找出有多少个不同的长度为m的严格上升子序列。（PS：相同子序列的定义为，每一个元素对应的下标都相同）

Input

输入数据第一行是个正整数T，表示总共有T组测试数据（T <= 5）; 每组数据第一行为n和m，以空格隔开（1 <= n <= 100, 1 <= m <= n）; 第二行为n个数，第i个数ai依次代表序列中的每个元素（1 <= ai <= 10^9）;

Output

对于每组数据，输出一行Case #x: y，x表示当前测试数据的序号（从1开始），y表示结果。需要注意的是，结果有可能很大，你需要将结果对1000000007(10^9+7)取余。

Sample Input

2 3 2 1 2 3 3 2 3 2 1

Sample Output

Case #1: 3 Case #2: 0

题解：

dp[i][j]代表前i个人j个递增子序列的长度；

if(a[i] > a[k])dp[i][j] = dp[i][j] + dp[k][j - 1](k < i);

代码：

 #include<iostream>

 #include<cmath>

 #include<cstring>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 const int MAXN = ;

 int dp[MAXN][MAXN];

 int a[MAXN];

 const int MOD = 1e9 + ;

 int main()

 {

     int T, kase = , n, m;

     scanf("%d", &T);

     while (T--) {

         scanf("%d%d", &n, &m);

         for (int i = ; i <= n; i++) {

             scanf("%d", a + i);

         }

         memset(dp, , sizeof(dp));

         for (int i = ; i <= n; i++) {

             dp[i][] = ;

             for (int j = ; j <= i; j++) {

                 for (int k = ; k < i; k++) {

                     if (a[k] < a[i]) {

                         dp[i][j] = (dp[i][j] + dp[k][j - ]) % MOD;

                     //  printf("%d %d\n",i ,j);

                     }

                 }

             }

         }

         int ans = ;

         for(int i = ; i <= n; i++)ans = (ans + dp[i][m]) % MOD; //wocao

         printf("Case #%d: %d\n", ++kase, ans);

     }

     return ;

 }

 /**************************************************************

     Problem: 1868

     User: handsomecui

     Language: C++

     Result: Accepted

     Time:18 ms

     Memory:1376 kb

 ****************************************************************/