题解 P2679 【子串】
Rumia
2016-11-17 11:38:51
十一行子串！（MQX最帅）
DP方程很简单，前面很多大神都写了，我主要是用sum处理了一下，然后可以滚动掉一维，于是成了2维11行dp
- A' 表示由串A前i个字符组成的串
- B' 表示由串B前j个字符组成的串
设$f(i,j,k)$为从A'中，顺序取k个不重复子串，首尾相接后与B'相等的方案数
$f(i,j,k)=\begin{cases}f(i-1,j,k) &,A_i\neq B_j\\ f(i-1,j,k)+f(i-1,j-1,k-1) &,A_i=B_j,A_{i-1}\neq B_{j-1}\\ f(i-1,j,k)+f(i-1,j-1,k-1)+f(i-2,j-2,k-1) &,A_i=B_j,A_{i-1}=B_{j-1},A_{i-2}\neq B_{j-2}\\ \vdots\\ \end{cases}$
设$p$
满足：
$\forall x\in[0,p], A_{i-x}=B_{j-x}$
$A_{i-p-1}\neq B_{j-p-1}$
则有：
$f(i,j,k)=\begin{cases}f(i-1,j,k)&,A_i\neq B_j\\ f(i-1,j,k)+\sum\limits^{p+1}_{t=1}f(i-t,j-t,k-1)&,A_i=B_j\end{cases}$
```cpp
#include<iostream>
long long f[201][201]={1},sum[201][201],n,m,ki;
char a[1001],b[201];
int main(){
std::cin>>n>>m>>ki>>a>>b;
for(int i=1;i<=n;i++)
for(int j=m;j>=1;j--)
for(int k=ki;k>=1;k--)
f[j][k]=(f[j][k]+ (sum[j][k]= a[i-1]==b[j-1]? sum[j-1][k]+f[j-1][k-1] : 0))%1000000007;
std::cout<<f[m][ki];
}