【題意】：求滿足一定升降序列的排列數的方案數。
【題解】：大連現場賽的E題，看到每個人的題解都說這是一道簡單dp。好吧，我承認我dp好菜，研究了幾天才弄懂。
狀態設定：dp[i][j] 表示長度為i的序列，以j結尾的滿足前i個條件的排列數。
這題需要理解的一個性質是當加入一個新的數n時，如果想把n放在前n-1個位置的任何一個，
并且不影響升降性質，只需要在之前方案中把當前在n位置的數x(n放前面必然有一個x要放在n的位置）
所有的大于等于x的數都加1即可。比如之前方案是(1,5,3,2,4),現在把3放在第6位。
則對應方案是(1,6,4,2,5,3)。[1和2不用變]
理解這個性質后，轉移就很容易想了。
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)的，利用部分和可以優化到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