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³）的算法：

 1 #include<cstdio>
 2 #include<cstring>
 3 #define N 1005
 4 #define M 1000000007
 5 using namespace std;
 6 typedef long long LL;
 7 char a[N];
 8 LL dp[N][N],len;
 9 int main(void){
10     while(~scanf("%s",a+1)){
11         memset(dp,0,sizeof(dp));
12         len=strlen(a+1);
13         for(LL i=1;i<=len;++i)
14             dp[0][i]=1;
15         for(LL i=1;i<=len;++i){
16             if(a[i]=='I'){
17                 for(LL j=1;j<=i;++j)
18                 if(dp[i-1][j]){
19                     for(LL k=j+1;k<=i+1;++k)
20                         dp[i][k]=(dp[i][k]+dp[i-1][j])%M;
21                 }
22             }else if(a[i]=='D'){
23                 for(LL j=1;j<=i;++j)
24                 if(dp[i-1][j]){
25                     for(LL k=1;k<=j;++k)
26                         dp[i][k]=(dp[i][k]+dp[i-1][j])%M;
27                 }
28             }else if(a[i]=='?'){
29                 for(LL j=1;j<=i;++j)
30                 if(dp[i-1][j]){
31                     for(LL k=1;k<=i+1;++k)
32                         dp[i][k]=(dp[i][k]+dp[i-1][j])%M;
33                 }
34             }
35         }
36         LL ans=0;
37         for(LL i=1;i<=len+1;++i)
38             ans=(ans+dp[len][i])%M;
39         printf("%I64d
",ans);
40     }
41 }

View Code

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

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

代码如下：

 1 #include<cstdio>
 2 #include<cstring>
 3 #define N 1005
 4 #define M 1000000007
 5 using namespace std;
 6 typedef long long LL;
 7 char a[N];
 8 LL dp[N][N],len,pre[N];
 9 int main(void){
10     while(~scanf("%s",a+1)){
11         memset(dp,0,sizeof(dp));
12         memset(pre,0,sizeof(pre));
13         len=strlen(a+1);
14         for(LL i=1;i<=len;++i){
15             dp[0][i]=1;
16             pre[i]=pre[i-1]+dp[0][i];
17         }
18         for(LL i=1;i<=len;++i){
19             if(a[i]=='I'){
20                 for(LL j=1;j<=i+1;++j)
21                     dp[i][j]=pre[j-1];
22             }else if(a[i]=='D'){
23                 for(LL j=1;j<=i+1;++j)
24                     dp[i][j]=(pre[i]-pre[j-1]+M)%M;
25             }else if(a[i]=='?'){
26                 for(LL j=1;j<=i+1;++j)
27                     dp[i][j]=pre[i];
28             }
29             for(LL j=1;j<=i+1;++j)
30                 pre[j]=(pre[j-1]+dp[i][j])%M;
31         }
32         printf("%I64d
",pre[len+1]);
33     }
34 }

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

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

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

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

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