2018-09-12
原题传送门（洛谷）https://www.luogu.org/problemnew/show/P2679
模拟考试的时候完全没有想到 正确的DP方程呢
本来写了一个大致是对的转移方程 结果算了一下空间 大概不够 就放弃了（第一维可以滚动 掉的啊喂 傻孩子啊） 愣是写了50分暴力
下面是五十分的原代码
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring> #define For(i,a,b) for(register int i=a;i<=b;++i)
#define Dwn(i,a,b) for(register int i=a;i>=b;--i)
#define Re register using namespace std;
const int md=1e9+; int na,nb,kx;
string As,Bs;
int sum=;
char c[];
int cf[]; int main(){
// freopen("ex2.in","r",stdin);
freopen("substring.in","r",stdin);
freopen("substring.out","w",stdout);
cin>>na>>nb>>kx;
cin>>As; cin>>Bs;
if(kx==){
int px=;
while(){
int p=As.find(Bs,px);
if(p==-)break;
sum++; px=p+;
if(sum>=md)sum%=md;
}
cout<<sum%md<<endl; return ;
}
if(kx==){
string s1,s2;
For(i,,nb-){
s1=""; s2="";
For(j,,i)s1=s1+Bs[j];
For(j,i+,nb-)s2=s2+Bs[j];
// cout<<s1<<" "<<s2<<" "<<sum<<endl; int px1,px2;
int sum2=;
px1=px2=; while(){
int p1=As.find(s1,px1);
if(p1==-)break;
sum2=;
px2=p1+s1.size();
if(p1>na-)break;
while(){
int p2=As.find(s2,px2);
if(p2==-)break;
sum2++; px2=p2+;
if(sum2>=md)sum2%=md;
}
sum+=sum2; if(sum>=md)sum%=md;
px1=p1+;
}
}
cout<<sum%md<<endl;
return ;
}
if(kx==nb){
For(i,,nb-)c[i+]=Bs[i],cf[i+]=;
For(i,,na-){
char ac=As[i];
Dwn(j,nb,){
if(ac==c[j]){
if(j==)cf[j]++;
else cf[j]+=cf[j-];
cf[j]%=md;
}
}
}
sum=cf[nb]%md;
cout<<sum<<endl;
return ;
}
}
当k=1，（即只能分一个字串） 直接s.find()去搜就好了
当k=2，（即分两个字串）还是暴力用find()去搜
然后 当k=m (即与B串等长）想了一个挺巧妙的方法。。 用 cf[i] 数组表示此时的B串前 i 位的方案数 按顺序 考虑 A串的一个字符
从后往前枚举 i 当 A[j]== B[i] cf[i]+=cf[i-1] (算了算了都是暴力 不看也罢
正确 方法
多维动归 ！
用我们 奥赛教练的话来说就是
每次只要一考到 多维动归 我就替学生捏一把汗 这道题是能否拿到绝对高分的关键！！
然鹅 模拟测试时我没做出来呢
好了 下面正经写题解
DP数组 f[i][j][k][0/1] 表示A的前i位 B的前j位 用了k个字串 A的第i个字串是否使用的方案数
那么我们很容易就可以得到转移方程
A[i]==B[j]
1. 不取（0）f[i][j][k][0] <-- f[i-1][j][k][0] + f[i-1][j][k][1]
2. 取 （1）f[i][j][k][1] <-- f[i-1][j-1][k][1] (与前方字符连成一个字串）+ f[i-1][j-1][k-1][1](自己单独另起一串）+ f[i-1][j-1][k-1][0]
A[i]!=B[j]
1. 不取（0）f[i][j][k][0] <-- f[i-1][j][k][0] + f[i-1][j][k][1]
2. 取 显然只能等于 0
初始边界 所有的 f[i][0][0][0]=1
然后愉快地把第一维 i 用滚动数组滚掉即可
复杂度 O(nmk)
附上代码
// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm> #define For(i,a,b) for(register int i=a;i<=b;++i)
#define Re register
using namespace std;
const int Na=1e3+,Nb=;
const int md=1e9+;
long long f[][Nb][Nb][];
char A[Na],B[Nb];
int na,nb,kx;
int main(){
// freopen("substring9.in","r",stdin);
// freopen("substring.out","w",stdout);
scanf("%d%d%d",&na,&nb,&kx);
scanf("%s",A+); scanf("%s",B+);
f[][][][]=f[][][][]=;
For(i,,na){
int now=i%;
For(j,,nb) For(k,,kx){
if(A[i]==B[j]){
f[now][j][k][]=(f[now^][j-][k][]+f[now^][j-][k-][]+f[now^][j-][k-][])%md;
f[now][j][k][]=(f[now^][j][k][]+f[now^][j][k][])%md;
}else{
f[now][j][k][]=;
f[now][j][k][]=(f[now^][j][k][]+f[now^][j][k][])%md;
}
}
}
long long fn=f[na%][nb][kx][]+f[na%][nb][kx][];
cout<<fn%md<<endl;
fclose(stdin); fclose(stdout);
return ; }