洛谷P2679 子串 （2015noip d2t2）【dp神题】【滚动数组】

 1 #include<iostream>
 2 #include<map>
 3 using namespace std;
 4 
 5 int n,m,k;
 6 char A[1005],B[205]; 
 7 long long mod = 1000000007;
 8 
 9 long long f[2][205][205],s[2][205][205];// s[i][j][k]代表A里前i个挑k个子串 拼成B里前j个的方案数,一定用a[i]
10                                   // f[i][j][k]可用可不用a[i] 
11                                     //滚动数组消掉i 
12         // f[i][0][0]=1
13 int main(){
14     cin>>n>>m>>k;
15     for(int i=1;i<=n;i++) cin>>A[i];
16     for(int i=1;i<=m;i++) cin>>B[i];
17     
18     int now=1,last=0;
19     f[0][0][0]=1;
20     for(int i=1;i<=n;i++){
21         f[now][0][0]=1;
22         for(int j=1;j<=min(i,m);j++){
23             for(int p=1;p<=min(j,k);p++){//目标每一个状态都有意义
24                 if( A[i]==B[j] ) s[now][j][p] =  (f[last][j-1][p-1]+s[last][j-1][p])%mod ;
25                 else s[now][j][p]=0;
26                 f[now][j][p] =  (s[now][j][p]+f[last][j][p])%mod;
27             }
28         }
29         now=!now; last=!last;
30     }
31     
32     cout<<f[last][m][k];
33     
34     return 0;
35 }