LOJ2424 NOIP2015 子串【DP】*

LOJ2424 NOIP2015 子串

题目大意是给你两个序列，在a序列中选出k段不重叠的子串组成b序列，问方案数

首先我们不考虑相邻的两段，把所有相邻段当成一段进行计算

然后设表示a使用了i为，b匹配到j位，一共有k段，当前这一位选不选的方案数

然后转移显然:

(条件 $a_i=b_j$ )
然后之后的dp就非常显然了

把i滚动数组掉就可以了

然后注意数组清零和j和k的枚举下界是0。。。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int Mod=1e9+7;
 4 const int N=1e3+10,M=2e2+10;
 5 #define fu(a,b,c) for(int a=b;a<=c;a++)
 6 int dp[2][M][M][2];
 7 int c[N][N];
 8 int n,m,k,ind=0;
 9 char a[N],b[N];
10 int add(int a,int b){return (a+b)%Mod;}
11 int mul(int a,int b){return 1ll*a*b%Mod;}
12 void init() {
13   fu(i,0,n)c[i][0]=1;
14   fu(i,1,n)fu(j,1,i)c[i][j]=add(c[i-1][j],c[i-1][j-1]);
15 }
16 int main() {
17   scanf("%d%d%d",&n,&m,&k);
18   scanf("%s%s",a+1,b+1);
19   init();
20   dp[ind][0][0][0]=1;
21   fu(i,1,n) {
22     ind^=1;
23     memset(dp[ind],0,sizeof(dp[ind]));
24     fu(j,0,min(i,m))
25       fu(k,0,j) {
26         dp[ind][j][k][0]=add(dp[ind^1][j][k][0],dp[ind^1][j][k][1]);
27         if(k==0||j==0||a[i]!=b[j])continue;
28         dp[ind][j][k][1]=add(dp[ind^1][j-1][k][1],dp[ind^1][j-1][k-1][0]);
29       }
30   }
31   int ans=0;
32   fu(i,1,k)ans=add(ans,mul(add(dp[ind][m][i][0],dp[ind][m][i][1]),c[m-i][k-i]));
33   printf("%d",ans);
34   return 0;
35 }

LOJ2424 NOIP2015 子串 【DP】*

LOJ2424 NOIP2015 子串

LOJ2424 NOIP2015 子串【DP】*