HDU 4055

大意：给出一个排列的上升下降的情况，求满足条件的序列数。

例如：321 对应着 DD, ID对应着： 231、132。

DP问题，分析待整理，本题个人觉得挺经典的。

 1 /*
 2 ID:esxgx1
 3 LANG:C++
 4 PROG:hdu4055
 5 */
 6 #include <cstdio>
 7 #include <cstring>
 8 #include <iostream>
 9 #include <algorithm>
10 using namespace std;
11 
12 int dp[1024][1024];
13 
14 #define MOD    1000000007
15 
16 int main(void)
17 {
18     #ifndef ONLINE_JUDGE
19     freopen("in.txt", "r", stdin);
20     #endif
21 
22     char s[1024];
23     while(scanf("%s", s) > 0) {
24         int len = strlen(s);
25         dp[0][0] = 1;
26         for(int i = 0 ; i < len; ++i) {
27             int i2 = i + 1;
28             if (s[i] == 'D') {
29                     dp[i2][i2] = 0;
30                     for(int j = i2; j--; )
31                         dp[i2][j] = (dp[i2][j+1] + dp[i2-1][j]) % MOD;
32             } else if (s[i] == 'I') {
33                     dp[i2][0] = 0;
34                     for(int j=1; j<=i2; ++j)
35                         dp[i2][j] = (dp[i2][j-1] + dp[i2-1][j-1]) % MOD;
36             } else {
37                     int sum = 0;
38                     for(int k =0 ; k<i2; ++k) sum = (sum + dp[i2-1][k]) % MOD;
39                     for(int j=0; j<=i2; ++j)
40                         dp[i2][j] = sum;
41             }
42         }
43         int sum = 0;
44         for(int i=0; i<=len; ++i) sum = (sum + dp[len][i]) % MOD;
45         printf("%d
", sum);
46     }
47     return 0;
48 }

2014-07-29 16:56:00

Accepted

4055

1437MS

4312K

975 B

G++