题解 P2679 【子串】
八重樱飞
2019-10-07 15:54:35
# 蒟蒻表示研究DP方程很久的说
尽管各位大佬都觉得此题DP方程很简单
但是可能也会有像我这样的蒟蒻看的不是很懂
于是在蒟蒻研究了很久之后，终于AC了
之后蒟蒻将会从动规的三要素讲起
## 关于阶段
由题可知，阶段应如此划分（~~蒟蒻认为~~）
A串的第i位 匹配到了B串第j位 使用了p个子串
（应该可以理解吧）
至于为什么？咱们看看题目
从A串中取出k个互不重叠的非空子串，把这k个子串按照出现的顺序依次连接起来得到一个新的字符串，并使得这个新串与B串相等
嗯嗯嗯，我相信各位都懂了吧
## 关于状态
状态一： A串第i位字符
状态二： B串第j位字符
状态三： 当前使用的子串数p（注意p<=k）
以及 状态四：a[i]是否能匹配得上b[j]
还有状态五，但是这个稍作悬念，下一栏再进一步分析
## 关于决策
但是由于状态四的不确定性，得分两种情况
1.a[i]=b[j]时
决策一：使用该字符匹配
决策二：不使用该字符匹配
2.a[i]!=b[j]时
只能不使用该字符匹配
由此可见，状态五便华丽丽地登场了
那就是 是否会使用该字符
我们可以用0表示不使用，1表示使用
## 综上所述 得出动态转移方程
1.a[i]=b[j]时
决策一：f[i][j][p][1]=f[i-1][j-1][p][1]+f[i-1][j-1][p-1][0]+f[i-1][j-1][p-1][1]
（~~代码里也有解释，不过不是很详尽~~）
对于上述的数组解释如下
f[i][j][p][1]:A串前i个使用了k个子串匹配到B串前j个，并且使用了当前a[i]的种数
f[i-1][j-1][p][1]:将当前字符纳入前一个子串，并使用前一个字符的种数
f[i-1][j-1][p-1][0]:将当前字符纳入新子串，但不使用前一个字符的种数
f[i-1][j-1][p-1][1]:将当前字符纳入新子串，并使用前一个字符的种数
对于上述方程的解释：
将该字符纳入前一个子串算一种情况（因为纳入前一个子串，故肯定是使用）
将该字符单独看成一个新子串算一种，而看成一个新子串，又分两种：第一种是不使用前一个字符，第二种是不使用前一个字符。（因为是新子串，所以前一个字符与当前字符是独立的，所以有两种）
决策二:f[i][j][p][0]=f[i-1][j][p][1]+f[i-1][j][p][0]
未使用该字符，故B子串匹配数仍为j，子串仍为k.
未使用该字符的种数即前一个字符使用的种数+前一个字符未使用的种数(继承上一阶段的）
2.a[i]!=b[j]时
f[i][j][p][1]=0
不能使用该字符，所以为0
f[i][j][p][0]=f[i-1][j][p][1]+f[i-1][j][p][0];
因为不能使用该字符，所以便继承上一阶段的值
## 提醒
数组 1000 * 200 * 200 * 2肯定会爆，故滚动第一维（因为第一维只有i和i-1）
最后答案应该为f[n][m][k][1]+f[n][m][k][0]相加
（最后一个字符使用和不使用是两种情况嘛，最终答案应该是他们之和）
## 上代码
于是，各位最爱的代码上线了
```cpp
#include<iostream>
#include<cstdio>
using namespace std;
int md=1000000007;
int n,m,k,f[2][222][222][2];
char a[1001],b[201];
int main()
{
int i,j,p;
scanf("%d%d%d",&n,&m,&k);
for(i=1;i<=n;i++)
cin>>a[i];
for(i=1;i<=m;i++)
cin>>b[i];
f[0][0][0][0]=1;
f[1][0][0][0]=1;//初始化，否则之后都得是0
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
for(p=1;p<=k;p++)
{
if(a[i]==b[j])
{
f[i%2][j][p][1]=(f[(i-1)%2][j-1][p][1]+f[(i-1)%2][j-1][p-1][0])%md+f[(i-1)%2][j-1][p-1][1]%md;
//f[i-1][j-1][p][1]:将当前字符纳入前一个子串，并使用前一个字符的种数
//f[i-1][j-1][p-1][0/1]:将当前字符纳入新子串，但不使用（使用）前一个字符的种数
f[i%2][j][p][1]%=md;
f[i%2][j][p][0]=f[(i-1)%2][j][p][1]+f[(i-1)%2][j][p][0];
//未使用该字符的种数即前一个字符使用的种数+前一个字符未使用的种数
f[i%2][j][p][0]%=md;
}
else
{
f[i%2][j][p][0]=f[(i-1)%2][j][p][1]+f[(i-1)%2][j][p][0];
f[i%2][j][p][0]%=md;
f[i%2][j][p][1]=0;//不能使用该字符
}
}
printf("%d",(f[n%2][m][k][1]+f[n%2][m][k][0])%md);
return 0;
}
```