Number String

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4055

定义状态：dp[i][j]为当strlen=i，数字结尾为j的方案数.

当为'I'时，dp[i][j]=∑dp[i-1][1...j-1];//若之前填过j，可以让前面j到i的数+1

当为'D'时，dp[i][j]=∑dp[i-1][j...i];

当为'?'时，dp[i][j]=∑dp[i-1][1...i].

于是我们有了O（n³）的算法：

 #include<cstdio>

 #include<cstring>

 #define N 1005

 #define M 1000000007

 using namespace std;

 typedef long long LL;

 char a[N];

 LL dp[N][N],len;

 int main(void){

     while(~scanf("%s",a+)){

         memset(dp,,sizeof(dp));

         len=strlen(a+);

         for(LL i=;i<=len;++i)

             dp[][i]=;

         for(LL i=;i<=len;++i){

             if(a[i]=='I'){

                 for(LL j=;j<=i;++j)

                 if(dp[i-][j]){

                     for(LL k=j+;k<=i+;++k)

                         dp[i][k]=(dp[i][k]+dp[i-][j])%M;

                 }

             }else if(a[i]=='D'){

                 for(LL j=;j<=i;++j)

                 if(dp[i-][j]){

                     for(LL k=;k<=j;++k)

                         dp[i][k]=(dp[i][k]+dp[i-][j])%M;

                 }

             }else if(a[i]=='?'){

                 for(LL j=;j<=i;++j)

                 if(dp[i-][j]){

                     for(LL k=;k<=i+;++k)

                         dp[i][k]=(dp[i][k]+dp[i-][j])%M;

                 }

             }

         }

         LL ans=;

         for(LL i=;i<=len+;++i)

             ans=(ans+dp[len][i])%M;

         printf("%I64d\n",ans);

     }

 }

但是这个复杂度是不能ac的，需要优化。

注意到状态转移的时候，出现了类似前缀和的性质，于是可以维护一个pre[N]数组，使复杂度达到O（n²）

代码如下：

 #include<cstdio>

 #include<cstring>

 #define N 1005

 #define M 1000000007

 using namespace std;

 typedef long long LL;

 char a[N];

 LL dp[N][N],len,pre[N];

 int main(void){

     while(~scanf("%s",a+)){

         memset(dp,,sizeof(dp));

         memset(pre,,sizeof(pre));

         len=strlen(a+);

         for(LL i=;i<=len;++i){

             dp[][i]=;

             pre[i]=pre[i-]+dp[][i];

         }

         for(LL i=;i<=len;++i){

             if(a[i]=='I'){

                 for(LL j=;j<=i+;++j)

                     dp[i][j]=pre[j-];

             }else if(a[i]=='D'){

                 for(LL j=;j<=i+;++j)

                     dp[i][j]=(pre[i]-pre[j-]+M)%M;

             }else if(a[i]=='?'){

                 for(LL j=;j<=i+;++j)

                     dp[i][j]=pre[i];

             }

             for(LL j=;j<=i+;++j)

                 pre[j]=(pre[j-]+dp[i][j])%M;

         }

         printf("%I64d\n",pre[len+]);

     }

 }

感觉dp的题目刚开始想出来的算法，要么会超时，要么会爆空间，需要优化。

然而我的优化方案是写完高复杂度代码后，按照转移方程的形式进行优化。

这样做的坏处是，优化完了方程面目全非，自己也不知道方程的意义...

可能是太弱了吧，继续加油~

//这两个星期金工实习，不用去上好爽~

巴特西

Number String

Number String

最新文章

热门文章