2011 Asia Dalian Regional Contest
题意：由数字1到n组成的所有排列中，问满足题目所给的n-1个字符的排列有多少个，如果第i字符是‘I’表示排列中的第i-1个数是小于第i个数的。如果是‘D’，则反之。
思路：刚开始完全没有思路。。。
其实做dp的话首先一定要确定好状态转移方程
状态转移方程： dp[i][j]表示在i个数时以j结尾的方案数，那么可以得到：
当s[i]=‘I‘或‘?‘时（表示增加），那么dp[i][j]+=dp[i-1][k](1=<k<j)
当s[i]=‘D‘或‘?‘时（表示减少），那么dp[i][j]+=dp[i-1][k](i>k>=j)
但是这样时间复杂度是O（n^3），会超时啊，所以引入sum[][]数组来记录前缀，使时间降为O（n^2）
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<stdlib.h> 6 using namespace std; 7 #define N 1006 8 #define MOD 1000000007 9 char s[N]; 10 int dp[N][N];//dp[i][j]表示在这个排列中第i个数字以j结尾的，满足条件的子排列有多少个。 11 int sum[N][N]; 12 int main() 13 { 14 while(scanf("%s",s+2)!=EOF) 15 { 16 int n=strlen(s+2); 17 memset(dp,0,sizeof(dp)); 18 memset(sum,0,sizeof(sum)); 19 dp[1][1]=sum[1][1]=1; 20 for(int i=2;i<=n+1;i++) 21 { 22 for(int j=1;j<=i;j++) 23 { 24 if(s[i]==‘I‘ || s[i]==‘?‘) 25 { 26 27 dp[i][j]=dp[i][j]+sum[i-1][j-1]; 28 dp[i][j]%=MOD; 29 } 30 if(s[i]==‘D‘ || s[i]==‘?‘) 31 { 32 33 dp[i][j]=dp[i][j]+(sum[i-1][i-1]-sum[i-1][j-1])%MOD+MOD; 34 dp[i][j]%=MOD; 35 } 36 sum[i][j]=(sum[i][j-1]+dp[i][j])%MOD; 37 } 38 39 } 40 41 printf("%d\n",sum[n+1][n+1]); 42 } 43 return 0; 44 }
原文：http://www.cnblogs.com/UniqueColor/p/4735443.html
