首页 > ACM题库 > HDU-杭电 > HDU 4055-Number String-动态规划-[解题报告]HOJ
2015
04-16

HDU 4055-Number String-动态规划-[解题报告]HOJ

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.

题目链接:Click here~~

题意:

给一个字符串,’I’ 和 ‘D‘ 代表排列中递增 or 递减,? 代表均可。

求满足这种条件的排列的方案数。

解题思路:

dp[i][j] 表示长度为 i ,以 j 为结尾的排列的方案数。

如果 str[i-1] == ’I‘  ,那么 dp[i][j] = dp[i-1][j-1] + dp[i-1][j-2] + … + dp[i-1][1]。

如果 str[i-1] == ‘D’,那么 dp[i][j] = dp[i-1][i-1] + dp[i-1][i-2] + … + dp[i-1][j]。

第一个式子比较好理解,只要在长度为 i-1 且结尾数字小于 j 的排列后面加个 j 就好了。

第二个式子,只要在长度为 i-1 且结尾数字大于等于 j 的排列中,把大于等于 j 的数字全部加1(不影响之前的递增和递减情况),后面再加个 j 就行了。

转移的复杂度可以通过用 sum 数组记录前缀和优化到 O(1)。

其实还可以用滚动数组优化空间复杂度。不贴了。

#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;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/dgq8211/article/details/8946394


  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.