Number String
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2007 Accepted Submission(s):
973
Problem Description
The signature of a permutation is a string that is
computed as follows: for each pair of consecutive elements of the permutation,
write down the letter 'I' (increasing) if the second element is greater than the
first one, otherwise write down the letter 'D' (decreasing). For example, the
signature of the permutation {3,1,2,7,4,6,5} is "DIIDID".
Your task is as follows: You are given a string describing the signature of many possible permutations, find out how many permutations satisfy this signature.
Note: For any positive integer n, a permutation of n elements is a sequence of length n that contains each of the integers 1 through n exactly once.
Your task is as follows: You are given a string describing the signature of many possible permutations, find out how many permutations satisfy this signature.
Note: For any positive integer n, a permutation of n elements is a sequence of length n that contains each of the integers 1 through n exactly once.
Input
Each test case consists of a string of 1 to 1000
characters long, containing only the letters 'I', 'D' or '?', representing a
permutation signature.
Each test case occupies exactly one single line, without leading or trailing spaces.
Proceed to the end of file. The '?' in these strings can be either 'I' or 'D'.
Each test case occupies exactly one single line, without leading or trailing spaces.
Proceed to the end of file. The '?' in these strings can be either 'I' or 'D'.
Output
For each test case, print the number of permutations
satisfying the signature on a single line. In case the result is too large,
print the remainder modulo 1000000007.
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.
Author
HONG, Qize
Source
/* dp方程的设定比较显然，dp[i][j]表示选了i个元素，最后一个是j的方案数。 但是在状态转移的时候，我们不得不考虑前面选了什么，也就是状态的设定是有后效性的， 所以考虑给状态再添一层含义：必须选前i个元素。 那么这样岂不是每次只能选i吗？那么第二维岂不是没有用了？ 所以我们考虑用j把i替换出来，那么在状态转移的时候就需要考虑放入i时，怎么替换能使原来的大小顺序保持不变。 将dp[i-1][j]的i-1个数的序列中 ≥j 的数都加1，这样i-1变成了i，j变成了j+1，而j自然就补在后面了。 处理I：dp[i][j] = Σdp[i-1][x]，其中1≤x≤j-1，可进一步简化，dp[i][j] = dp[i][j-1]+dp[i-1][j-1] 处理D：dp[i][j] = Σdp[i-1][x]，其中j≤x≤i-1，可进一步简化，dp[i][j] = dp[i-1][j+1]+dp[i-1][j] 处理?：dp[i][j] = Σdp[i-1][x]，其中1≤x≤i-1 */ #include<iostream> #include<cstdio> #include<cstring> using namespace std; #define maxn 1010 #define mod 1000000007 char s[maxn]; int dp[maxn][maxn]; int main(){ while(scanf("%s",s+1)!=EOF){ int n=strlen(s+1);n++; int ans=0; memset(dp,0,sizeof(dp)); dp[1][1]=1; for(int i=2;i<=n;i++){ if(s[i-1]=='I') for(int j=2;j<=i;j++) dp[i][j]=(dp[i][j-1]+dp[i-1][j-1])%mod; else if(s[i-1]=='D') for(int j=i-1;j>=1;j--) dp[i][j]=(dp[i][j+1]+dp[i-1][j])%mod; else { int sum=0; for(int j=1;j<i;j++)sum=(sum+dp[i-1][j])%mod; for(int j=1;j<=i;j++)dp[i][j]=sum; } } for(int i=1;i<=n;i++)ans=(ans+dp[n][i])%mod; printf("%d ",ans); } }