题意：一个1~n的序列，分别用'I','D'表示序列的升降，如{1,2,4,3}，则是属于IID的情况，而1~4中属于IID情况的可以有很多不同的序列，给出序列的I、D表现形式（‘?’表示‘I’或‘D’都可以），求出满足这样要求的有多少种。
例如：
Sample Input II ID DI DD ?D ?? Sample Output 1 2 2 1 3 6 Hint Permutation {1,2,3} has signature "II". Permutations {1,3,2} and {2,3,1} have signature "ID". Permutations {3,1,2} and {2,1,3} have signature "DI". Permutation {3,2,1} has signature "DD". "?D" can be either "ID" or "DD". "??" gives all possible permutations of length 3.
可以用dp[i][j]表示：处理完第i位，序列末尾位j的序列共有多少个。最后的结果为sigma{dp[N][i]}，1≤i≤N
处理dp[1~i][]的过程中i是依次1~n相加。处理完dp[i-1][]后，加入的数即为i，而dp[i][j]是要将i放进去j换出来，而这里有一种将i放进去j换出来，同时不影响升降顺序的方法是：
将dp[i-1][j]的i-1个数的序列中 ≥j 的数都加1，这样i-1变成了i，j变成了j+1，而j自然就补在后面了。
所以对”ID“序列依次处理即可，初始条件：dp[1][1] = 1; 即只有{1}。
处理‘I’：dp[i][j] = sigma{dp[i-1][x]}，其中1≤x≤j-1，可进一步简化，dp[i][j] = dp[i-1][j-1]+dp[i-1][j-1]
处理‘D’：dp[i][j] = sigma{dp[i-1][x]}，其中j≤x≤i-1，可进一步简化，dp[i][j] = dp[i-1][j+1]+dp[i-1][j]
处理‘?’：dp[i][j] = sigma{dp[i-1][x]}，其中1≤x≤i-1，直接计算
处理过程中在注意边界和取模问题就可以了，附上代码
View Code
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 #include <algorithm> 6 #include <cmath> 7 #include <string> 8 #include <vector> 9 #include <queue> 10 #include <set> 11 #include <map> 12 #define MAXN 1010 13 using namespace std; 14 const int mod = 1000000007; 15 char str[MAXN]; 16 17 int dp[MAXN][MAXN]; 18 int main(){ 19 int N; 20 char ch; 21 while(~scanf("%s",str)){ 22 N=strlen(str)+1; 23 memset(dp,0,sizeof(dp)); 24 dp[1][1]=1; 25 for(int i=2;i<=N;i++){ 26 ch = str[i-2]; 27 if(ch=='?'){ 28 int sum=0; 29 for(int j=1;j<=i-1;j++)sum = (sum+dp[i-1][j])%mod; 30 for(int j=1;j<=i;j++){ 31 dp[i][j]=sum; 32 } 33 } 34 else if(ch=='I'){ 35 for(int j=2;j<=i;j++){ 36 dp[i][j]=(dp[i][j-1]+dp[i-1][j-1])%mod; 37 } 38 } 39 else{ 40 for(int j=i-1;j>=1;j--){ 41 dp[i][j]=(dp[i][j+1]+dp[i-1][j])%mod; 42 } 43 } 44 } 45 int res=0; 46 for(int i=1;i<=N;i++){ 47 res = (res+dp[N][i])%mod; 48 } 49 printf("%d\n",res); 50 } 51 return 0; 52 }
另外一道题SGU489，求法和上道题类似~~【该死去年过的大连赛区的题，今年做这题居然想不起来】
题意：给出一个n，求1~n的排列中，满足IDIDID……或DIDIDID……的序列有多少个。
dp[i][j][0]：处理完第i个数后最后一位数是j，且倒数第二位至最后一位的趋势是下降；
dp[i][j][1]：处理完第i个数后最后一位数是j，且倒数第二位至最后一位的趋势是上升。
转移方程：
dp[i][j][0] = sigma{dp[i-1][x][1]}，其中j≤x≤i-1，可进一步简化，dp[i][j][0] = dp[i-1][j+1][0]+dp[i-1][j][1]
dp[i][j][1] = sigma{dp[i-1][x][0]}，其中1≤x≤j-1，可进一步简化，dp[i][j][1] = dp[i-1][j-1][1]+dp[i-1][j-1][0]
最后求sigma{dp[N][i][0]+dp[N][i][1]}，1≤i≤N。注意初始条件为dp[1][1][0] = dp[1][1][1] = 1;所以n==1时要特判一下。当然还需要用到滚动数组优化一下空间，上一题其实也可以用滚动数组，不过范围不大也没必要，代码如下：
Time: 953 MS
View Code
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<algorithm> 5 #include<cstring> 6 using namespace std; 7 8 int dp[2][10005][2]; 9 int main(){ 10 int n, m, i, j; 11 int ans; 12 while(~scanf("%d%d",&n,&m)){ 13 if(n==1){ 14 printf("%d\n",n%m);continue; 15 } 16 memset(dp,0,sizeof(dp)); 17 dp[1][1][0] = dp[1][1][1] = 1; 18 for(i=2;i<=n;i++){ 19 for(j=i;j>=1;j--){ 20 dp[i&1][j][0] = (dp[i&1][j+1][0]+dp[(i-1)&1][j][1])%m; 21 } 22 for(j=1;j<=i;j++){ 23 dp[i&1][j][1] = (dp[i&1][j-1][1]+dp[(i-1)&1][j-1][0])%m; 24 } 25 } 26 ans = 0; 27 for(j=1;j<=n;j++){ 28 ans = (ans+(dp[n&1][j][0]+dp[n&1][j][1])%m)%m;//这里很坑爹，一定要两个相加后取模，不然就暴int了 29 //当然如果直接用long long就不会了，不过dp数组用long long的超空间问题不能实现，那么三个连加就不知道什么情况了。 30 } 31 printf("%d\n",ans%m); 32 } 33 return 0; 34 }
还有一个优化版本，利用的性质是对称性：dp[i][j][0] = dp[i][i-j][1]。
最后求sigma{dp[N][i][0]+dp[N][i][1]}，1≤i≤N。也就是sigma{dp[N][i][0]}*2了，所以可以少计算dp[i][j][0]。
Time: 500 MS
View Code
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<algorithm> 5 #include<cstring> 6 using namespace std; 7 8 int dp[2][10005]; 9 int main(){ 10 int n, m, i, j; 11 int ans; 12 while(~scanf("%d%d",&n,&m)){ 13 if(n==1){ 14 printf("%d\n",n%m);continue; 15 } 16 memset(dp,0,sizeof(dp)); 17 dp[1][1] = 1; 18 for(i=2;i<=n;i++){ 19 for(j=i;j>=1;j--){ 20 dp[i&1][j] = (dp[i&1][j+1]+dp[(i-1)&1][i-j])%m; 21 } 22 } 23 ans = 0; 24 for(j=1;j<=n;j++){ 25 ans = (ans+dp[n&1][j])%m; 26 } 27 printf("%d\n",(ans+ans)%m); 28 } 29 return 0; 30 }