Number String
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4055
dp
定义状态：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（n3）的算法：
#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（n2）
代码如下：
#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的题目刚开始想出来的算法，要么会超时，要么会爆空间，需要优化。
然而我的优化方案是写完高复杂度代码后，按照转移方程的形式进行优化。
这样做的坏处是，优化完了方程面目全非，自己也不知道方程的意义...
可能是太弱了吧，继续加油~
//这两个星期金工实习，不用去上好爽~