fzoj 2170 花生的序列

Accept: 41 Submit: 127
Time Limit: 3000 mSec Memory Limit : 32768 KB

Problem Description

“我需要一個案件！！！”，沒有案件卷福快瘋了。花生不忍心看卷福這個樣子，他決定幫卷福找點事情做。

花生拿了兩個長度為N的相同的序列，序列都為WB(WBWBWB...)相間，並且由W開頭。他將兩個序列並在了一起，其中屬於同個序列的元素相對位置不變。花生高興的把新序列拿給卷福，要求卷福給每個元素標上1或2編號，表示這個元素是原來的第幾個序列的元素。

卷福看完花生的序列，哭笑不得。“笨蛋！你難道不知道這個標號不唯一麼！那你知道有多少種不同的標號方案麼？”

可憐的花生給自己挖了個坑。快來幫他解決這個問題！

Input

輸入第一行包含一個整數t，表示輸入組數。<喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+w7/X6cr9vt212tK70NDOqtK7uPbV+8r9TigxPD1OPD0zMDAwKaOsse3KvsO/uPbUrdDywdC1xLOktsihozwvcD4KPHA+vdPPwsC00rvQ0M6q0ru49ta7sPy6rKGvV6GvLCChr0Khr7XE19a3+7Suo6yzpLbIzqoyKk6hozwvcD4KCjxoMj48aW1nIHNyYz0="https://www.aspphp.online/bianchen/UploadFiles_4619/201701/2017012114344918.gif" alt="\"> Output

輸出一個整數占一行，為標號的方案數。由於答案比較大，請將答案mod 1000000007。

Sample Input

Sample Output

這道題網絡賽時做不出來。。。

回去想了一下。。和看了別人的解題報告。。突然發現別人寫的可能有點簡潔。

所以我就在寫多一篇。。

題解：dp[i][j]代表第一個串選擇了i個第二個串選擇了j個有多少種可能。。

然後就有了dp[i][j] = (dp[i-1][j]+dp[i][j-1])%MOD;

代表選擇到了第i+j的字符串時。。這個字符串可以放在第一個串或者第二個串。。

當然你還要判斷能不能放進去。。因為wbwb要相間的。。而w只能放在奇數處。b只能放在偶輸處

例如第一個串放了2個那第三個一定是放w了。。就是3是奇數。所以放的時候還要判斷能不能放。

#include 
#include
#include 

using namespace std;
#define MOD 1000000007
int dp[3002][3002];
char ch[6003];
int main(int argc, const char * argv[])
{

    int t,i,j;
    int n;
    cin>>t;
    while(t--) {
        cin>>n;
        scanf("%s",ch+1);
          memset(dp,0,sizeof(dp));
        dp[0][0] = 1;
        for(i=0;i<=n;i++)
            for (j=0; j<=n; j++) {
                  if(i==0 && j==0) continue;
                  int sum = 0;
                  if(ch[i+j]=='W') {
                        if(i&1)
                              sum = (sum+dp[i-1][j])%MOD;
                        if(j&1)
                              sum = (sum+dp[i][j-1])%MOD;
                        
                        dp[i][j] = sum%MOD;
                  }
                  else {
                        if(i>0 && (i&1)==0)
                              sum = (sum+dp[i-1][j])%MOD;
                        if(j>0 && (j&1)==0)
                              sum = (sum+dp[i][j-1])%MOD;
                        
                        dp[i][j] = sum%MOD;
                  }
            }
          cout<

其實這個代碼是超內存的。。當然題目的數據其實是沒3000.n最多達到1000.。所以只要將dp[1003][1003]就能過了

但是其實可以發現這個dp每一次都是對於上一行或者這一行遞推的（dp[i-1][],dp[i][]）
所以我們其實是可以將二維dp降到一維的
就好像01背包問題將前i件的維數去掉了。。
然後就有了。。
#include 
#include
#include 

using namespace std;
#define MOD 1000000007
int dp[3002];
int v[3002];
char ch[6003];
int main(int argc, const char * argv[])
{

    int t,i,j;
    int n;
    cin>>t;
    while(t--) {
        cin>>n;
        scanf("%s",ch+1);
        dp[0] = 1;
        v[0] = 1;
        for(i=0;i<=n;i++)
            for (j=0; j<=n; j++) {
                  if(i==0 && j==0) continue;
                  int sum = 0;
                  if(ch[i+j]=='W') {
                        if(i&1)
                              sum = (sum+v[j])%MOD;
                        if(j&1)
                              sum = (sum+dp[j-1])%MOD;
                        
                        v[j] = dp[j] = sum%MOD;
                  }
                  else {
                        if(i>0 && (i&1)==0)
                              sum = (sum+v[j])%MOD;
                        if(j>0 && (j&1)==0)
                              sum = (sum+dp[j-1])%MOD;
                        
                        v[j] = dp[j] = sum%MOD;
                  }
            }
          cout<

時間雖然沒優化多少。。但是空間就變成了200多k。。。