p2679 子串-白红宇

p2679 子串

阅读量：6463 次

发布时间：2019-06-23

本文共 1098 字，大约阅读时间需要 3 分钟。

分析

我们可以用dp[i][j][k][0/1]表示A串考虑到第i个，B串考虑到第j个，一共取了k个子串，现在的A[i]是否被选的方案数。我们需要将第一维滚动一下。具体转移见代码。

代码

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 #include
                  
                   using namespace std;const int mod = 1e9+7;#define add(x,y) x=(x+y)%modint dp[2][1100][210][2],n,m,t;char A[1100],B[1100];int main(){ int i,j,k,now=0; scanf("%d%d%d",&n,&m,&t); scanf("%s",A); scanf("%s",B); for(i=n;i>0;i--)A[i]=A[i-1]; for(i=m;i>0;i--)B[i]=B[i-1]; dp[now][0][0][0]=1; for(i=1;i<=n;i++){ now^=1; memset(dp[now],0,sizeof(dp[now])); dp[now][0][0][0]=1; for(j=1;j<=m;j++) for(k=1;k<=t;k++){ add(dp[now][j][k][0], (dp[now^1][j][k][0]+dp[now^1][j][k][1])%mod); if(A[i]==B[j]){ add(dp[now][j][k][1],dp[now^1][j-1][k][1]); add(dp[now][j][k][1], (dp[now^1][j-1][k-1][0]+dp[now^1][j-1][k-1][1])%mod); }else dp[now][j][k][1]=0; } } printf("%d\n",(dp[now][m][t][1]+dp[now][m][t][0])%mod); return 0;}