HDU4055 - number string（DP）

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

思路：dp[i][j]表示處理前i個字符以j結尾可能的序列數。

當a[i]=='I'時，dp[i][j]=sum(dp[i-1][k]),（1<=k<=j-1）， 可進一步化為dp[i][j-1]+dp[i-1][j-1]。

當a[i]=='D'時，dp[i][j]=sum(dp[i-1][k]),(j<=k<=i-1)，可進一步化為dp[i][j+1]+dp[i-1][j]。

當a[i]=='?'時，dp[i][j]=sum(dp[i-1][k]),(1<=k<=i-1)。

#include<cstdio>
#include<cstring>
using namespace std;
const int N = 1e3 + 5;
const int mod = 1e9 + 7;
char a[N];
int dp[N][N];
int main()
{while(~scanf("%s",a+2)){memset(dp,0,sizeof(dp));int len = strlen(a+2) + 1;dp[1][1] = 1;for(int i = 2 ;i <= len ;i++){if(a[i] == 'I'){for(int j = 2 ;j <= i ;j++)dp[i][j] = (dp[i][j-1] + dp[i-1][j-1]) % mod;}else if(a[i] == 'D'){for(int j = i-1 ;j >= 1 ;j--)dp[i][j] = (dp[i][j+1] + dp[i-1][j]) % mod;}else{int sum = 0;for(int j = 1 ;j <= i-1 ;j++)sum = (sum + dp[i-1][j]) % mod;for(int j = 1 ;j <= i ;j++)dp[i][j] = sum;}}int ans = 0;for(int i = 1 ;i <= len ;i++)ans = (ans + dp[len][i]) % mod;printf("%d\n",ans);}return 0;
}

?

?