2015
04-16

Number String

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.

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 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’.

II
ID
DI
DD
?D
??

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 为结尾的排列的方案数。

#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

const int N = 1e3 + 2;
const int mod = 1e9 + 7;

int dp[N][N],sum[N][N];

char str[N];

int main()
{
dp[1][1] = sum[1][1] = 1;
while(~scanf("%s",str+1))
{
int n = strlen(str+1) + 1;
for(int i=2;i<=n;i++)
{
for(int j=1;j<=i;j++)
{
if(str[i-1] == 'I')
dp[i][j] = sum[i-1][j-1];
else if(str[i-1] == 'D')
dp[i][j] = (sum[i-1][i-1] - sum[i-1][j-1] + mod) % mod;
else
dp[i][j] = sum[i-1][i-1];
sum[i][j] = (sum[i][j-1] + dp[i][j]) % mod;
}
}
printf("%d\n",sum[n][n]);
}
return 0;
}


1. 有限自动机在ACM中是必须掌握的算法，实际上在面试当中几乎不可能让你单独的去实现这个算法，如果有题目要用到有限自动机来降低时间复杂度，那么这种面试题应该属于很难的级别了。

2. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.