【題意】：求滿足一定升降序列的排列數(shù)的方案數(shù)。

【題解】：大連現(xiàn)場(chǎng)賽的E題，看到每個(gè)人的題解都說(shuō)這是一道簡(jiǎn)單dp。好吧，我承認(rèn)我dp好菜，研究了幾天才弄懂。
              狀態(tài)設(shè)定：dp[i][j] 表示長(zhǎng)度為i的序列，以j結(jié)尾的滿足前i個(gè)條件的排列數(shù)。

              
              這題需要理解的一個(gè)性質(zhì)是當(dāng)加入一個(gè)新的數(shù)n時(shí)，如果想把n放在前n-1個(gè)位置的任何一個(gè)，

              并且不影響升降性質(zhì)，只需要在之前方案中把當(dāng)前在n位置的數(shù)x(n放前面必然有一個(gè)x要放在n的位置）

              所有的大于等于x的數(shù)都加1即可。比如之前方案是(1,5,3,2,4),現(xiàn)在把3放在第6位。

              則對(duì)應(yīng)方案是(1,6,4,2,5,3)。[1和2不用變]
              

              理解這個(gè)性質(zhì)后，轉(zhuǎn)移就很容易想了。
              if(s[i] == 'I') dp[i][j] = sum(dp[i][k]), 1<=k<j
              if(s[i] == 'D') dp[i][j] = sum(dp[i][k]), j<=k<=i
              if(s[i] == '?') dp[i][j] = sum(dp[i][k]), 1<=k<=i
              樸素做法是O(n^3)的，利用部分和可以優(yōu)化到O(n^2).

【代碼】:
 1 #include "iostream"
 2 #include "cstdio"
 3 #include "cstring"
 4 using namespace std;
 5 #define maxn 1010
 6 const int MOD = 1000000007;
 7 char s[maxn];
 8 int dp[maxn][maxn], sum[maxn][maxn];
 9 
10 void solve() {
11     int len = strlen(s+2);
12     memset(dp, 0, sizeof(dp));
13     memset(sum, 0, sizeof(sum));
14     dp[1][1] = sum[1][1] = 1;
15     for(int i = 2; i < len + 2; i++) {
16         for(int j = 1; j <= i; j++) {
17             if(s[i] == 'I') dp[i][j] = sum[i-1][j-1];
18             else if(s[i] == 'D') dp[i][j] = (sum[i-1][i-1] - sum[i-1][j-1] + MOD) % MOD;
19             else dp[i][j] = sum[i-1][i-1];
20             sum[i][j] = (sum[i][j-1] + dp[i][j]) % MOD;
21         }
22     }
23     printf("%d\n", sum[len+1][len+1]);
24 }
25 
26 int main() {
27     while(~scanf("%s", s + 2)) solve();
28     return 0;
29 }
30