难点在于：
1. f(i, j, k)中定义a[i]必取
2. g(j, k)定义为用k个子串取到b[j]的方案总数
3. 参照01背包问题通过j从m循环至1去掉f(i)这一维
4. 在考虑状态转移时先分为a[i]能不能取，能取就一定取，再按照a[i]是否是一个新的子串开始划分，若不是，则a[i]算在f(i-1, j-1, k-1)中，用g(j-1, k-1)即可统计

#include<iostream>
#include<algorithm>
#include<cstdio> 
#include<cstring>
#include<vector>
using namespace std;

const int mod=1000000007;
string a, b;
int f[205][205], g[205][205];//f[j][l]表示取a[i]中l个子串至b[i]的方案数，g[j][l]表示到a[i]为止取l个子串至b[j]的方案数总和 

int main(){
    int n, m, k;
    cin>>n>>m>>k;
    cin>>a>>b;
    f[0][0]=g[0][0]=1;
    for(int i=1;i<=n;i++)
            for(int j=m;j>=1;j--)
                    for(int l=1;l<=k;l++){
                            if(a[i-1]!=b[j-1]){ f[j][l]=0; continue; }
                            f[j][l]=(f[j-1][l]+g[j-1][l-1])%mod;
                            g[j][l]=(g[j][l]+f[j][l])%mod;
                     }
    cout<<g[m][k]<<endl;
    return 0;
}

NOIP2015Day2T2
一道好好的DP题
我们用dp[i][j][k]表示在B串中匹配i个，在A串中匹配到的位置为j，共使用k个子串的方案总数，
则dp[i][j][k]=Σdp[i-1][j']k-1 +dp[i-1][j-1][k]
那么，对于Σ可以用前缀和优化，这样的时间就可以卡进去了
但是空间还是要炸，所以我们采用滚动数组来优化空间

#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;
const int N=1000+5,M=200+5;
const int mod=1e9+7;
char s1[N],s2[M];
int n,m,K;
int dp[2][N][M],sum[2][N][M];
//dp[i][j][k]=Σdp[i-1][j'][k-1](1<=j'<=j-1) +dp[i-1][j-1][k] 
int main(){
    scanf("%d%d%d%s%s",&n,&m,&K,s1+1,s2+1);
    memset(dp,0,sizeof dp);
    memset(sum,0,sizeof sum);
    int I=0,J=1;
    for (int i=1;i<=n;i++){
        if (s2[1]==s1[i])
            dp[0][i][1]=1;
        sum[0][i][1]=sum[0][i-1][1]+dp[0][i][1];
    }
    for (int i=2;i<=m;i++,I^=1,J^=1){
        memset(dp[J],0,sizeof dp[J]);
        memset(sum[J],0,sizeof sum[J]);
        for (int j=1;j<=n;j++){
            if (s2[i]!=s1[j])
                continue;
            for (int k=1;k<=K;k++)
                if (j>=2)
                    dp[J][j][k]=(sum[I][j-1][k-1]+dp[I][j-1][k])%mod;
                else
                    dp[J][j][k]=dp[I][j-1][k];
        }
        for (int k=1;k<=K;k++)
            for (int j=1;j<=n;j++)
                sum[J][j][k]=(sum[J][j-1][k]+dp[J][j][k])%mod;
    }
    printf("%d",sum[I][n][K]);
    return 0;
}

/*滚动数组优化内存，前缀和优化时间效率*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
const int MAXN=400+3;
const int mod=1000000007;
using namespace std;
long long f[3][MAXN][MAXN][3],sum[MAXN][MAXN],n,m,k;
char aa[1200],bb[1200],a[1200],b[1200];
int main()
{
scanf("%d%d%d",&n,&m,&k);
scanf("%s",&aa);
for(int i=0;i<strlen(aa);++i) a[i+1]=aa[i];
scanf("%s",&bb);
for(int i=0;i<strlen(bb);++i) b[i+1]=bb[i];
f[0][0][0][0]=1;
int x=0;
long long ans=0;
for(int i=1;i<=n;++i)
{
x^=1;
for(int j=0;j<=m;++j)
for(int l=0;l<=k;++l)
f[x][j][l][1]=f[x][j][l][0]=0;
for(int j=1;j<=m;++j)
for(int l=1;l<=k;++l)
{
if(a[i]==b[j])
{
if(j==1&&l==1) f[x][j][l][1]=1;
else f[x][j][l][1]=(f[x^1][j-1][l][1]+f[x^1][j-1][l-1][0]+f[x^1][j-1][l-1][1])%mod;
f[x][j][l][0]=sum[j][l]%mod;
sum[j][l]=(sum[j][l]+f[x][j][l][1])%mod;

}

else
f[x][j][l][0]=sum[j][l]%mod;
}

//printf("f[%d][%d][%d][%d]:%d\n",i,m,k,1,f[x][m][k][1]);
ans=(ans+f[x][m][k][1])%mod;
}
printf("%lld\n",ans);
return 0;
}

#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
const int mod = 1000000007;
char a[1005], b[205];
long long f[2][205][205], g[2][205][205];
int main() {
    int n, m, k, now = 1;
    cin >> n >> m >> k;
    cin >> a + 1 >> b + 1;
    for(int i = 1; i <= n; i++) {
        now ^= 1;
        for(int j = 1; j <= m; j++)
            for(int l = 1; l <= k; l++) {
                if(a[i] == b[j])
                    g[now][j][l] = (f[now ^ 1][j - 1][l - 1] + g[now ^ 1][j - 1][l]) % mod;
                else
                    g[now][j][l] = 0;
                if(a[i] == b[j] && l == 1 && j == 1)
                    g[now][j][l] = 1;
                f[now][j][l] = (g[now][j][l] + f[now ^ 1][j][l]) % mod;
            }
    }
    cout << f[now][m][k] << endl;
    return 0;
}

实在看不懂各位大神的初始化
于是自己更改一下

#include<cstdio>
#include<cstring>
#include<algorithm>
//vijos上没必要开滚动数组也能过
using namespace std;

const int MAXN = 1005,MAXM = 205,Mo = int(1e9) + 7;

char A[MAXN],B[MAXM];
int F[2][MAXN][MAXM],N,M,K;

int main()
{
scanf("%d%d%d", &N, &M, &K);
scanf("%s", A + 1);
scanf("%s", B + 1);
int cur = 0;
for(int i = 0;i <= N;i ++)
F[0][i][0] = 1;
for(int k = 1;k <= K;k ++)
{
cur ^= 1;
for(int i = 0;i <= N;i ++)
F[cur][i][k - 1] = 0;
for(int j = k;j <= M;j ++)
for(int i = j;i <= N;i ++)
{
if (A[i] == B[j])
{
F[cur][i][j] = (F[cur][i - 1][j - 1] + F[cur][i - 1][j]) % Mo;
F[cur][i][j] = (F[cur][i][j] + F[cur ^ 1][i - 1][j - 1]) % Mo;
if (i >= 2) F[cur][i][j] = (F[cur][i][j] - F[cur][i - 2][j - 1] + Mo) % Mo;
} else
F[cur][i][j] = F[cur][i - 1][j];
}
}
printf("%d\n", F[cur][N][M]);
return 0;
}

能过noip官方数据和vijos数据的

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
using namespace std;
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define clr(x,c) memset(x,c,sizeof(x))
#define ll long long
int read(){
int x=0;char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) x=x*10+c-'0',c=getchar();
return x;
}
const int nmax=205;
const int maxn=1005;
const int inf=0x7f7f7f7f;
const int mod=1e9+7;
int f[maxn][nmax],g[maxn][nmax],cur[maxn][nmax];
char a[maxn],b[nmax];
void M(int &a){
if(a>=mod) a-=mod;
else if(a<0) a+=mod;
}
int main(){
int n=read(),m=read(),K=read();
scanf("%s%s",a+1,b+1);a[0]='.';b[0]='$';
rep(i,1,n) rep(j,1,min(i,m)) if(a[i]==b[j]){
cur[i][j]=1;
rep(t,1,min(j,i)) if(a[i-t]!=b[j-t]) {
cur[i][j]=t;break;
}
}
rep(i,0,n) g[i][0]=1;
rep(i,1,n){
rep(j,1,min(i,m)) {
M(f[i][j]+=f[i-1][j]);
if(cur[i][j]) M(f[i][j]+=g[i-cur[i][j]][j-cur[i][j]]);
}
}
rep(i,0,n) g[i][0]=0;
if(K!=1)rep(i,1,n) rep(j,1,m) M(g[i][j]+=g[i-1][j-1]+f[i][j]),f[i][j]=0;
int ta,tb,tmp;
rep(k,2,K){
rep(i,k,n){
rep(j,k,min(i,m)){
M(f[i][j]+=f[i-1][j]);
if(a[i]==b[j]){
ta=i-cur[i][j]-1;tb=j-cur[i][j]-1;
if(ta<0||tb<0) tmp=0;
else tmp=g[ta][tb];
M(f[i][j]+=g[i-1][j-1]-tmp);
}
}
}
if(k!=K) rep(i,1,n) rep(j,1,m) M(g[i][j]=g[i-1][j-1]+f[i][j]),f[i][j]=0;
}
printf("%d\n",f[n][m]);
return 0;
}


这个数据太诡异了，我一开始把题目理解成“字符串中只有小写字母ab”居然过了八个点。
```c++
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

const int INF = 1000000000;
const int MOD = 1000000007;
const int maxn = 1000 + 10;
const int maxm = 200 + 10;
int n, m, k;
int s1[maxn], s2[maxm];
int d[2][maxm][maxm];
int g[2][maxm][maxm];

int readchar () {
char c; cin >> c;
return c - 'a';
}

int plus_mod (int a, int b) {
return ((long long) a + b) % MOD;
}

int main ()
{
// freopen("in.txt", "r", stdin);
cin >> n >> m >> k;
for (int i = 1; i <= n; i++) s1[i] = readchar();
for (int i = 1; i <= m; i++) s2[i] = readchar();

d[0][0][0] = d[1][0][0] = 1;
int t = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1;j <= m; j++)
for (int x = 1; x <= k; x++) {
if (s1[i] == s2[j])
g[t][j][x] = plus_mod(g[t^1][j-1][x], d[t^1][j-1][x-1]);
else g[t][j][x] = 0;

d[t][j][x] = plus_mod(d[t^1][j][x], g[t][j][x]);
}
t ^= 1;
}
cout << d[t^1][m][k];
return 0;
}
```

其实dp[i,j,k]表示a串i和b串j相等且必须匹配的方案数也可以
dp[i,j,k]=∑dp[i1,j-1,k-1]+dpi-1,j-1,k
dp[i,j,k]=0(a[i]<>b[j])
ans=∑dpi,m,k
这是O(nmkn)的算法
时间上过不去
加个前缀和sum
sum[i,j,k]为∑dp[i1,j-1,k-1]
sum[i,j,k]=sum[i-1,j,k]+dp[i,j,k]
开开心心地在vijios上交了

然后看楼上楼上楼上楼上、、、
发现空间爆掉了、
再开滚动数组

把i-1滚掉
ps:dp[0,0,0]=1;sum[0,0,0]=1;

其实dp[i,j,k]表示a串i和b串j相等且必须匹配的方案数也可以
dp[i,j,k]=∑dp[i1,j-1,k-1]+dpi-1,j-1,k
dp[i,j,k]=0(a[i]<>b[j])
ans=∑dpi,m,k
这是O(nmkn)的算法
时间上过不去
加个前缀和sum
sum[i,j,k]为∑dp[i1,j-1,k-1]
sum[i,j,k]=sum[i-1,j,k]+dp[i,j,k]
开开心心地在vijios上交了

然后看楼上楼上楼上楼上、、、
发现空间爆掉了、
再开滚动数组

把i-1滚掉
ps:dp[0,0,0]=1;sum[0,0,0]=1;

其实dp[i,j,k]表示a串i和b串j相等且必须匹配的方案数也可以
dp[i,j,k]=∑dp[i1,j-1,k-1]+dpi-1,j-1,k
dp[i,j,k]=0(a[i]<>b[j])
ans=∑dpi,m,k
这是O(nmkn)的算法
时间上过不去
加个前缀和sum
sum[i,j,k]为∑dp[i1,j-1,k-1]
sum[i,j,k]=sum[i-1,j,k]+dp[i,j,k]
开开心心地在vijios上交了

然后看楼上楼上楼上楼上、、、
发现空间爆掉了、
再开滚动数组

把i-1滚掉
ps:dp[0,0,0]=1;sum[0,0,0]=1;

为什么开位运算滚动数组还没开赋值滚动数组快、、、

f[i,j,k]表示a串前i个选k份拼成b串前j个的方案数，易知:
f[i,j,k]=f[i-1,j,k]
当a[i]=b[j]时有f[i,j,k]=f[i,j,k]+f[i-1,j-1,k-1]
当(a[i]=b[j]) and (a[i-1]=b[j-1])时有f[i,j,k]=f[i,j,k]+f[i-1,j-1,k-1]+f[i-1,j-1,k]
当时这样会WA，以样例为例:

6 3 1
aabaab
aab

f[5,2,1]≠f[4,1,0]+f[4,1,1] {f[4,1,0]=0,f[4,1,1]=4,f[5,2,1]=2}

原因在于f[i,j,k]中包含a串第i个不取的方案，所以可以想到在f中分离出一个g[i,j,k]出来，表示a串第i位必须取得情况，这时就有推导方程:
当a[i]=b[j]时，g[i,j,k]=f[i-1,j-1,k-1]+g[i-1,j-1,k]
同理，当a[i]≠b[j]时，g[i,j,k]=0
于是f[i,j,k]=f[i-1,j,k]+g[i,j,k];

数据比较小，不用滚动数组也可以，数组也就[1000][200][200]

const
maxn=1005;
qumo=1000000007;
var
ans,i,j,k,n,m,l:longint;
temp,f:array[0..2,0..maxn,0..205] of longint;
s1,s2:string;
begin
readln(n,m,l);
readln(s1);
readln(s2);
ans:=0;
f[0,0,0]:=1;
temp[0,0,0]:=1;
for i:=0 to n do
temp[0,i,0]:=1;
for k:=1 to l do
begin
for i:=1 to n do
begin
for j:=1 to m do
begin
if s1[j]=s2[j] then
begin
f[k and 1,i,j]:=temp[(k+1)and 1,i-1,j-1];
if s1[i-1]=s2[j-1] then f[k and 1,i,j]:=(f[k and 1,i,j]+f[k and 1,i-1,j-1])mod qumo;
if f[k and 1,i,j]>=qumo then f[k and 1,i,j]:= f[k and 1,i,j] mod qumo;
end;
temp[k and 1,i,j]:=(temp[k and 1,i,j]+f[k and 1,i,j]) mod qumo + temp[k and 1,i-1,j];
if (temp[k and 1,i,j]>qumo) then temp[k and 1,i,j]:=temp[k and 1,i,j]mod qumo;
end;
end;
end;
for i:=1 to n do
ans:=(ans+f[l and 1,i,m]) mod qumo;
writeln(ans);
end.
哪位大牛可不可以帮忙看看哪儿错了？？改了几天了改不出来了。。。。。。。。。TAT

#include <cstdio>
#include <algorithm>
using namespace std;
int n, m, k, i, j, t, l;
char A[1005], B[1005];
int D[2][205][1005];

int main() {
scanf("%i %i %i %s %s", &n, &m, &k, B + 1, A + 1);
fill(D[0][0], D[0][1], 1);
for (t = 1; t <= k; t++) {
fill(D[t % 2][0], D[t % 2][m + 1], 0);
for (i = t; i <= m; i++)
for (j = i; j <= n; j++) {
D[t % 2][i][j] = D[t % 2][i][j - 1];
for (l = 1; l <= i && A[i - l + 1] == B[j - l + 1]; l++)
D[t % 2][i][j] =
(D[t % 2][i][j] + D[(t + 1) % 2][i - l][j - l]) % 1000000007;
}
}
printf("%i", D[k % 2][m][n]);
return 0;
}

#include <cstdio>
#include <algorithm>
using namespace std;
int n, m, k, i, j, t, l;
char A[1005], B[1005];
int D[2][205][1005];

int main() {
scanf("%i %i %i %s %s", &n, &m, &k, B + 1, A + 1);
fill(D[0][0], D[0][1], 1);
for (t = 1; t <= k; t++) {
fill(D[t % 2][0], D[t % 2][m + 1], 0);
for (i = t; i <= m; i++)
for (j = i; j <= n; j++) {
D[t % 2][i][j] = D[t % 2][i][j - 1];
for (l = 1; l <= i && A[i - l + 1] == B[j - l + 1]; l++)
D[t % 2][i][j] =
(D[t % 2][i][j] + D[(t + 1) % 2][i - l][j - l]) % 1000000007;
}
}
printf("%i", D[k % 2][m][n]);
return 0;
}

#include<stdio.h>
#include<iostream>
#include<cstring>
#include<cstdlib>
using namespace std;
const int mod=1000000007;
long long dp[205][205],sum[205][205];
char a[1005],b[205];

int main()
{
memset(dp,0,sizeof(dp));
memset(sum,0,sizeof(sum));
int n,m,k;
scanf("%d%d%d",&n,&m,&k);
scanf("%s%s",a+1,b+1);
a[0]=0; b[0]=1;

for (int i=1; i<=n; i++)
{

for (int j=m; j>=1; j--)
if (a[i]==b[j])
{

if (j==1) dp[1][1]=1;
for (int l=k; l>=1; l--)
{

if (j!=1) dp[j][l]=0;
if (a[i-1]==b[j-1])
{
dp[j][l]=(dp[j-1][l]+dp[j][l])% mod;

}

dp[j][l]=(dp[j][l]+sum[j-1][l-1]) % mod;
sum[j][l]=(sum[j][l]+dp[j][l])% mod ;
}

}
}
printf("%lld\n",sum[m][k]);

return 0;
}
dp+前缀和优化+滚动数组
其实vijos上空间没有定，其实这道题只有128MB，O（nkm）虽然不会爆时间但会爆空间。

设f(i, j, k)为a串前i个中选出k个字串拼成b串前j个的方案数，g(i, j, k)是a串第i个必须用的方案数
当且仅当a[i] == b[j]，g[i][j][k] = g[i - 1][j - 1][k] + f[i - 1][j - 1][k - 1]，因为若不等于则第i个一定不用，所以此时g[i][j][k] = 0
g[i - 1][j - 1][k]代表第i个用于接上上一个字串
f[i - 1][j - 1][k - 1]代表第i个用于新开一个字串
显然f[i][j][k] = g[i][j][k] + f[i - 1][j][k]，因为此时有两个决策，要么用第i个，要么不用第i个
最终答案为f[n][m][k]
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#define MOD 1000000007

using namespace std;

int n, m, K;
long long f[2][205][205], g[2][205][205];
char a[1005], b[205];

int main(int argc, const char *argv[]) {
scanf("%d %d %d", &n, &m, &K);
scanf("%s%s", a, b);
for (int i = n; i >= 1; --i) a[i] = a[i - 1];
for (int i = m; i >= 1; --i) b[i] = b[i - 1];
int now, prev;
now = 1;
prev = 0;
f[0][0][0] = 1;
for (int i = 1; i <= n; ++i) {
f[now][0][0] = 1;
for (int j = 1; j <= m; ++j) {
for (int k = 1; k <= K; ++k) {
if (a[i] == b[j])
g[now][j][k] = (f[prev][j - 1][k - 1] + g[prev][j - 1][k]) % MOD;
else
g[now][j][k] = 0;
f[now][j][k] = (g[now][j][k] + f[prev][j][k]) % MOD;
}
}
swap(now, prev);
}
printf("%lld\n", f[prev][m][K]);
return 0;
}

记录信息
评测状态 Accepted
题目 P1982 子串
递交时间 2015-11-19 21:32:19
代码语言 C++
评测机 VijosEx
消耗时间 904 ms
消耗内存 3596 KiB
评测时间 2015-11-19 21:32:21
评测结果
编译成功

foo.cpp: In function 'int main()':
foo.cpp:35:24: warning: unknown conversion type character 'l' in format [-Wformat=]
printf("%lld\n",ans);
^
foo.cpp:35:24: warning: too many arguments for format [-Wformat-extra-args]
测试数据 #0: Accepted, time = 0 ms, mem = 3588 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 3588 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 3596 KiB, score = 10
测试数据 #3: Accepted, time = 31 ms, mem = 3588 KiB, score = 10
测试数据 #4: Accepted, time = 31 ms, mem = 3596 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 3596 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 3588 KiB, score = 10
测试数据 #7: Accepted, time = 203 ms, mem = 3592 KiB, score = 10
测试数据 #8: Accepted, time = 203 ms, mem = 3588 KiB, score = 10
测试数据 #9: Accepted, time = 406 ms, mem = 3592 KiB, score = 10
Accepted, time = 904 ms, mem = 3596 KiB, score = 100
代码
#include <iostream>
#include <cstdio>
using namespace std;
long long dp[2][210][1010];
const long long mod=1000000007;
int pre,now,len1,len2,k;
char s1[1010],s2[210];
int main()
{
scanf("%d%d%d",&len1,&len2,&k);
scanf("%s",s1+1);
scanf("%s",s2+1);
long long tot=0;
for(int kn=1;kn<=k;kn++)
{
pre=(kn+1)%2;
now=kn%2;
tot=0;
for(int i=1;i<=len2;tot=0,i++)
for(int j=1;j<=len1;j++)
{ dp[now][i][j]=0;
if(s2[i]==s1[j]){
if(i==1){
if(kn==1)
dp[now][i][j]=1;
continue;
}
dp[now][i][j]=(tot+dp[now][i][j]+dp[now][i-1][j-1])%mod;

}tot=(tot+dp[pre][i-1][j])%mod;
}

}
long long ans=0;
for(int i=1;i<=len1;i++)ans=(ans+dp[now][len2][i])%mod;
printf("%lld\n",ans);
return 0;
}