【题意】：求满足一定升降序列的排列数的方案数。
【题解】：大连现场赛的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