【1】题解：P2679 [NOIP2015 提高组] 子串【动态规划】
ExFish
·
·
题解
代码是我大号的，然后题解发到这里。
看到这道题，首先考虑暴力动态规划。
怎么做呢？
首先得有两维，i 和 j，是两个字符串的处理指针。
然后，这题有个 k 记录子串，那我们就不能定义成 k，冲突了，得改成 l，记录的是分了几个子串。
接着，我们还需要一维，记录是否选，我们叫这一位 z。
我们就得到了一个状态 f_{i,j,l,z}，记录状态。
首先初始化。要是 j 指针没动，为 0，那都是合法的。
所以，f_{i,0,0,0}=1。
接着，转移。
枚举各个指针就不说了，直接正着就可以。
先分析 v=1 的情况。
然后是 a_i\neq b_j。
我们发现，这样看起来不合法，所以 v=0，那么 f_{i,j,l,1}=0。
否则，a_i=b_j。
那么怎么写呢？
要是从 $f_{i-1,j-1,l-1}$ 这个分段的转移而来，那么有可能这里断开了，有可能是紧接着上一个子串的末尾。那么，可以从 $f_{i-1,j-1,l-1,0}$ 与 $f_{i-1,j-1,l-1,1}$ 转移，方法很简单，就是加法。
下一个，$v=0$。
那么，我们只需要从 $f_{i-1,j,l,0/1}$ 转移，毕竟没有开新的段。
分析完了，记得取模。
然后是答案，就是 $f_{n,m,k,0/1}$。
```cpp
#include<bits/stdc++.h>
//#include<bits/extc++.h>
using namespace std;
//using namespace __gnu_pbds;
//#define arr array<int,3>
//#define int long long
//#define pb push_back
//#define double long double
//#define map unordered_map
//#pragma GCC optimize(2,3,"Ofast","inline")
const int N=1010,M=210,P=1e9+7,MOD=998244353;
const double PI=3.1415926,EPS=0.00001;
int n,m,k,f[N][M][M][2];
string a,b;
signed main(){
cin>>n>>m>>k;
cin>>a;
cin>>b;
a=" "+a;
b=" "+b;
for(int i=0;i<=n;i++)
f[i][0][0][0]=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
for(int l=1;l<=k;l++){
f[i][j][l][0]=f[i-1][j][l][0]+
f[i-1][j][l][1];
if(a[i]==b[j]){
f[i][j][l][1]=f[i-1][j-1][l][1]+
f[i-1][j-1][l-1][0]+
f[i-1][j-1][l-1][1];
}else f[i][j][l][1]=0;
f[i][j][l][0]%=P;
f[i][j][l][1]%=P;
}
}
}
cout<<(f[n][m][k][0]+f[n][m][k][1])%P;
return 0;
}
//note:
```
结束了吗？
简单分析~~试错~~发现会爆空间，那么直接滚动就结束了。
```cpp
#include<bits/stdc++.h>
//#include<bits/extc++.h>
using namespace std;
//using namespace __gnu_pbds;
//#define arr array<int,3>
#define int long long
//#define pb push_back
//#define double long double
//#define map unordered_map
//#pragma GCC optimize(2,3,"Ofast","inline")
const int N=1010,M=210,P=1e9+7,MOD=998244353;
const double PI=3.1415926,EPS=0.00001;
int n,m,k,f[2][M][M][2];
string a,b;
int rnd(int i){
return (i+2)%2;
}
signed main(){
cin>>n>>m>>k;
cin>>a;
cin>>b;
a=" "+a;
b=" "+b;
for(int i=0,r=0;i<=n;i++,r=rnd(i))
f[r][0][0][0]=1;
for(int i=1,r=1,y=0;i<=n;i++,r=rnd(i),y=rnd(i-1)){
for(int j=1;j<=m;j++){
for(int l=1;l<=k;l++){
f[r][j][l][0]=f[y][j][l][0]+
f[y][j][l][1];
if(a[i]==b[j]){
f[r][j][l][1]=f[y][j-1][l][1]+
f[y][j-1][l-1][0]+
f[y][j-1][l-1][1];
}else f[r][j][l][1]=0;
f[r][j][l][0]%=P;
f[r][j][l][1]%=P;
}
}
}
n=rnd(n);
cout<<(f[n][m][k][0]+f[n][m][k][1])%P;
return 0;
}
//note:
```
好的，终于写完了！感谢阅读。