原題： 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的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。