首页 > 代码库 > ZOJ3543 Number String 动态规划

ZOJ3543 Number String 动态规划

2024-07-13 02:19:42   222人阅读

ZOJ3543 Number String 

状态f[i][j]表示长度为I的全排列，符合字符串的要求，最后一位数字是j的方案数。

重点在要始终保持是f算的排列的数量，然后转移时用这些推出来新的情况。

就是j<=i

从长度是i-1的排列推长度是i的时候。因为确定了最后一位以后，前面不考虑数值，考虑名次还是一个i-1的排列的某一个。所以，如果要再最后加一个j，可以考虑认为是把前面大于等于j的数字都加一，就得到i的一个排列。

对于‘I‘或者‘?‘

　　f[i][j]+=f[i][2..j-1]

对于‘D‘或者‘?‘

　　f[i][j]+=f[i][j..i-1]

 

#include <iostream>#include <cstdio>#include <cstring>using namespace std;const long long MOD  = 1000000007;const int maxn = 1000 + 10 ;char s[maxn];long long f[maxn][maxn],sum[maxn];int main(){    while(scanf("%s",s)!=EOF){        int len = strlen(s);        int n = len + 1 ;        memset(f,0,sizeof(f));        memset(f,0,sizeof(f));        f[1][1]=1;        for(int i=1;i<=n;i++) sum[i]=1;        for(int i=2;i<=n;i++){            if(s[i-2]==‘I‘ || s[i-2]==‘?‘)                for(int j=2;j<=i;j++)                    f[i][j]=(f[i][j]+sum[j-1])%MOD;            if(s[i-2]==‘D‘ || s[i-2]==‘?‘)                for(int j=1;j<i;j++)                    f[i][j]=((sum[i-1]-sum[j-1]+MOD)%MOD+f[i][j])%MOD;            for(int j=1;j<=i;j++)                sum[j]=(sum[j-1]+f[i][j])%MOD;        }        printf("%lld\n",sum[n]);    }    return 0;}


联系
我们