ZOJ-3543不错的dp

墨蓝 2022-04-22 02:26 130阅读 0赞

--------------------

title: ZOJ-3543不错的dp  
date: 2018-11-01 16:40:58  
tags:

*  dp  
    categoties: “算法”

--------------------

题意：

给长为n-1字符串，包括‘I’,‘D’,’?'三个字符，含义分别是：

*  ‘I’比前面的数大
 *  ‘D’比前面的数小
 *  ‘？’不受限制

问题是有多少1~n的全排列满足这个关系串。

思路：

感觉挺难想的。设dp\[i\]\[j\]代表1~i的全排列，以j数字结尾，并且满足这个关系串的种类数。

那么对于长度为i+1，如果是字符‘D’

dp\[i+1\]\[j\]=sum(dp\[i\]\[k\]) k=j~i-1

**因为我们已经保证了i-1是满足的，当我们添加j使长度变为i，并且也要满足，就相当于前面大于等于j的数都+1，这样就变成了1~i满足关系串的全排列**

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int mo=1000000007;
    const int N=1e3+10;
    ll dp[N][N];
    ll sum[N];
    char s[N];
    
    int main(){
        while(~scanf("%s", s+2)){
            int n=strlen(s+2)+1;
    
            for(int i=1; i<=n; i++)
                for(int j=1; j<=n; j++)
                    dp[i][j]=0;
            dp[1][1]=1;
    
            for(int i=2; i<=n; i++){
    
                if(s[i]=='D'){
                    for(int j=i-1; j>=1; j--)
                        dp[i][j]=(dp[i][j+1]+dp[i-1][j])%mo;
                }
                else if(s[i]=='I'){
                    for(int j=2; j<=i; j++)
                        dp[i][j]=(dp[i][j-1]+dp[i-1][j-1])%mo;
                }
                else{
                    ll sum=0;
                    for(int j=1; j<i; j++) sum=(sum+dp[i-1][j])%mo;
                    for(int j=1; j<=i; j++) dp[i][j]=sum;
                }
            }
            ll sum=0;
            for(int i=1; i<=n; i++)
                sum=(sum+dp[n][i])%mo;
            printf("%lld\n", sum);
        }
    
        return 0;
    }