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.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+w7/X6cr9vt212tK70NDOqtK7uPbV+8r9TigxPD1OPD0zMDAwKaOsse3KvsO/uPbUrdDywdC1xLOktsihozwvcD4KPHA+vdPPwsC00rvQ0M6q0ru49ta7sPy6rKGvV6GvLCChr0Khr7XE19a3+7Suo6yzpLbIzqoyKk6hozwvcD4KCjxoMj48aW1nIHNyYz0="https://www.cppentry.com/upload_files/article/49/1_liob8__.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。。。