2014 Super Training #10 D 花生的序列 --DP

原题： FZU 2170 http://acm.fzu.edu.cn/problem.php?pid=2170

这题确实是当时没读懂题目，连样例都没想通，所以没做了，所以还是感觉这样散漫的做不好，有些题目明明很简单，却因为没看懂而放弃了，甚至去玩了，这样达不到太大的效果。

解法：

定义： dp[i][j]：前i个字母中有j个是属于第一个序列的标号方案种数。

则当遇到'B'时，因为要满足WB依次间歇出现，所以前面属于第一个序列的个数应该为奇数，即j&1时转移。当属于第二个序列的个数为奇数时（(i-j)&1）也要转移，因为这个B有可能属于第二个序列。当遇到'W'时反之。

用滚动数组节省空间。

代码：

#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <cstdlib> #include <algorithm> #define Mod 1000000007 using namespace std; #define N 6007int dp[2][N]; char ss[N];int main() {int n,i,j;int now;int t;scanf("%d",&t);while(t--){scanf("%d",&n);scanf("%s",ss);memset(dp,0,sizeof(dp));dp[0][0] = 1;for(i=0,now=1;i<2*n;i++,now=1-now){memset(dp[now],0,sizeof(dp[now]));if(ss[i] == 'B'){for(j=0;j<=n;j++){if(j&1)dp[now][j+1] = (dp[now][j+1]+dp[i&1][j])%Mod;if((i-j)&1)dp[now][j] = (dp[now][j]+dp[i&1][j])%Mod;}}else{for(j=0;j<=n;j++){if((j&1) == 0)dp[now][j+1] = (dp[now][j+1]+dp[i&1][j])%Mod;if(((i-j)&1) == 0)dp[now][j] = (dp[now][j]+dp[i&1][j])%Mod;}}}printf("%d\n",dp[0][n]);}return 0; } View Code

 

转载于:https://www.cnblogs.com/whatbeg/p/3832266.html

总结

以上是生活随笔为你收集整理的2014 Super Training #10 D 花生的序列 --DP的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。