hdu 4055 Number String(有点思维的DP)

Number StringTime Limit: 10000/5000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1016    Accepted Submission(s): 440


Problem DescriptionInputOutputSample InputSample OutputAuthorSourceRecommend#include <iostream>#include<stdio.h>#include<string.h>using namespace std;const int maxn=1010;const int mod=1000000007;char st[maxn];int dp[2][maxn],sum[2][maxn];int main(){ int i,j,len,v,u; sum[1][0]=sum[0][0]=0; while(~scanf("%s",st+2)) { v=0; len=strlen(st+2); dp[0][1]=sum[0][1]=1; for(i=2;i<=len+1;i++)//第一个数前没有数所以从2开始。一直到len+1 { u=v^1; for(j=1;j<=i;j++) { if(st[i]=='I') dp[u][j]=sum[v][j-1]; else if(st[i]=='D') dp[u][j]=(sum[v][i-1]-sum[v][j-1]+mod)%mod;//由于取模可能使大的变小 else dp[u][j]=sum[v][i-1]; sum[u][j]=(dp[u][j]+sum[u][j-1])%mod; //printf("sum[%d][%d]:%d\n",i,j,sum[v^1][j]); } v=u; } printf("%d\n",sum[v][len+1]); } return 0;}

感想：想了大半个晚上。终于想通点了。DP做着还不是那么顺手。还是题做少了啊。不过我不会放弃的。坚持一定会有效果。加油！