计数dp hdu 4055 Number String

红太狼 2022-08-19 04:49 157阅读 0赞

嗯，什么是计数dp我也不知道，这是第一次遇见类似的题目。

题意：给一个只含‘I','D','?'三种字符的字符串，I表示当前数字大于前面的数字，D表示当前的数字小于前面一位的数字，？表示当前位既可以小于又可以大于。问1~n的排列中有多少个满足该字符串。

分析：看题意就觉得像是dp，果然是的。dp\[i\]\[j\]表示的是前i个数字的排列中以数字j结尾的排列个数。

那么递推关系是什么呢。

当str\[i-1\] == 'I' 时表示第i为的数字大于i-1位的数字，我们可以看到，dp\[i\]\[j\] = dp\[i-1\]\[1\]+dp\[i-1\]\[2\]+......+dp\[i-1\]\[j-1\];

当str\[i-1\] == 'D' 时表示第i为的数字小于i-1位的数字，我们可以看到，dp\[i\]\[j\] = dp\[i-1\]\[j+1\]+dp\[i-1\]\[j+2\]+......+dp\[i-1\]\[i\]; 但是我们可以注意到，

dp\[i-1\]\[i\]是不存在的，前i-1个数字中是不会有i数字出现的。我们考虑到，将前i-1个数字的所有排列中，大于等于j的数字都加1的话，是不会改变排列方案数的，所以这时候dp\[i\]\[j\] = dp\[i-1\]\[j\]+dp\[i-1\]\[j+1\]+......+dp\[i-1\]\[i-1\];

但是这样的话复杂度是O(n^3)，会超时，所以我们增加一个数组sum\[i\]\[j\]来记录前缀和就可以了。sum\[i\]\[j\] 表示的是dp\[i\]\[1\]+dp\[i\]\[2\]+......+dp\[i\]\[j\]

#include <iostream>
    #include <cstdio>
    #include <cmath>
    #include <string>
    #include <cstring>
    #include <queue>
    #include <algorithm>
    using namespace std;
    
    #define mod 1000000007
    int const maxn = 1005;
    char str[maxn];
    long long dp[maxn][maxn];
    long long sum[maxn][maxn];
    //dp[i][j] 表示的是前i个数字的排列中以数字j结尾的排列个数
    //sum[i][j] 表示的是dp[i][1]+dp[i][2]+......+dp[i][j]
    
    int main()
    {
        while(scanf("%s",str+1)!=EOF)
        {
            int n = strlen(str+1)+1;
            //要计算的长度比字符串的长度大1
            dp[1][1] = 1 ; //一个数字以1结尾有一种情况
            sum[1][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] = (dp[i][j] + sum[i][j-1] + mod ) % mod ;
                }
            }
            printf("%I64d\n",sum[n][n]);
        }
        return 0;
    }