P2679 [NOIP2015 提高组] 子串
方杰123
·
·
个人记录
题目在这里
思路
如果s1_{i}=s2_{j}那么这对相同字母可以与上个在同一子串，也可以与前面的在不同子串。
设dp_{i,j,k}表示s1走到i，s2走到j，总共有k个子串被选。
接下来是重点：
1. 对于DP，首先要考虑数组的初始值与起点。如此处初始值都为0，起点$dp_{0,0,0}=1$。
2. 对于空间不足的，观察dp方程式进行滚动，且dp时进行重置。如这里k维可以滚动。
3. 对于时间不足的，一般对计算的维度优化，如这里的$\sum_{l=j-1}^{i}dp_{l,j-1,k-1}$可以用前缀和优化。除此之外还有其他优化（如数据结构）。
4. 结果不一定是$dp_{n}$，这里是前缀和。
## code
```cpp
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mod=1000000007;
int read(){
int x=0,f=1;char c=getchar();
while(c>'9' || c<'0'){if(c=='-')f=-1;c=getchar();}
while(c>='0' && c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
return x*f;
}
ll dp[1010][202][2],n,m,K,ans,sum[1010][202][2];//wei tou k;
char s1[1010],s2[202];
int main(){
n=read(),m=read(),K=read();
cin>>s1+1>>s2+1;dp[0][0][0]=1;for(int i=0;i<=n;i++)sum[i][0][0]=1;
for(int k=1;k<=K;k++){
for(int j=0;j<=m;j++)
for(int i=j;i<=n;i++)dp[i][j][k&1]=sum[i][j][k&1]=0;
for(int j=1;j<=m;j++){
for(int i=j;i<=n;i++){
if(s1[i]==s2[j]){
dp[i][j][k&1]=(dp[i][j][k&1]+dp[i-1][j-1][k&1])%mod;
dp[i][j][k&1]=(dp[i][j][k&1]+sum[i-1][j-1][(k-1)&1])%mod;
}
sum[i][j][k&1]+=(sum[i-1][j][k&1]+dp[i][j][k&1])%mod;//这里别放进if里。调很久了。
}
}
}
printf("%lld\n",sum[n][m][K&1]);
return 0;
}
```