关键词：
感谢http://blog.csdn.net/gengmingrui/article/details/49849023
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxn 1050 #define maxm 250 #define mod 1000000007 using namespace std; int n,m,l,f[2][maxn][maxm],s[2][maxn][maxm],ret; char a[maxn],b[maxm]; int main() { scanf("%d%d%d",&n,&m,&l); scanf("%s",a+1);scanf("%s",b+1); f[0][0][0]=s[0][0][0]=1; for (int i=1;i<=n;i++) s[0][i][0]=1; for (int k=1;k<=l;k++) { memset(f[k&1],0,sizeof(f[k&1])); memset(s[k&1],0,sizeof(s[k&1])); for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) { if (a[i]==b[j]) { f[k&1][i][j]=s[(k&1)^1][i-1][j-1]; if (a[i-1]==b[j-1]) f[k&1][i][j]=(f[k&1][i][j]+f[k&1][i-1][j-1])%mod; } s[k&1][i][j]=((s[k&1][i][j]+f[k&1][i][j])%mod+s[k&1][i-1][j])%mod; } } int ans=0; for (int i=1;i<=n;i++) ans=(ans+f[l&1][i][m])%mod; printf("%d ",ans); return 0; }
vijos1425子串清除题解
Vijos1425子串清除 题解 描述：我们定义字符串A是字符串B的子串当且仅当我们能在B串中找到A串。现在给你一个字符串A，和另外一个字符串B，要你每次从B串中从左至右找第一个A串，并从B串中删除它，直到A串不为B串的子... 查看详情
2016vijos1-1兔子的字符串（后缀数组+二分+哈希）(代码片段)
...串，至多将其划分为n部分，每一部分取出字典序最大的子串ci，最小化最大的ci 先看一个简化版的问题：给一个串s，再给一个s的子串t，问能否通过将串划分为k个部分，使t成为划分后的s的字典序最大子串 对于这个... 查看详情
[noip2015提高组]子串
...n的A串和长度为m的B串。现在要从A串中取出k个互不重叠的子串，使它们按顺序相连后得到B串。问有多少种方案。解题思路：DP。设f[i][j[[k][0]表示A的前i个字符匹配B的前j个字符，划分成k段，且当前A串这个字符不取的情况下的方... 查看详情
vijos在vijos的自己的域中创建题目(代码片段)
创建属于自己的域https://vijos.org/填入对应信息即可。创建题目点击题库往下拉，点击创建题目进入题目之后，点击设置接下来就是重点，配置数据点：（如果想直接用，后面有捷径。）写一个正确答案... 查看详情
vijos1057盖房子
二次联通门: Vijos1057盖房子 /*Vijos1057盖房子简单的dp当前点(i,j)所能构成的最大的正方形的边长为点(i-1,j-1)与(i,j-1),(i-1,j)三点中最小的边长构成..一遍递推,一边取最大即可*/#include<cstdio>#defineMax1009inlineintmin(inta,intb){... 查看详情
vijos1412多人背包
01背包+归并看的题解 https://vijos.org/p/1412/solution#include<cstdio>#include<cstring>usingnamespacestd;inta[205];intb[205];intf[5005][55];intk,n,v;voidwork(int*aa,int*bb,intc){intt[105];intt 查看详情
vijos1285&1283&1282&1284佳佳的魔法药水/魔杖/魔法照片/魔法阵
题目链接：https://vijos.org/p/1285https://vijos.org/p/1283https://vijos.org/p/1282https://vijos.org/p/1284 查看详情
vijos1001
按照题意模拟即可。#include<string>#include<iostream>#include<algorithm>usingnamespacestd;intmain(){stringname;intn,tot=0,ans=-1;cin>>n;for(inti=1;i<=n;i+=1){stringna;intva=0,k1,k2,k3 查看详情
vijos1104采药
不用说了，裸的01背包。#include<cstdio>#include<cctype>#include<algorithm>usingnamespacestd;inlineintread(){charc;while(c=getchar(),!isdigit(c));intx=c-‘0‘;while(c=getchar(),isdigit(c))x=x*10 查看详情
ural1982.electrificationplan（并查集）
题目链接：http://acm.timus.ru/problem.aspx?space=1&num=1982Somecountryhas n cities.Thegovernmenthasdecidedtoelectrifyallthesecities.Atfirst,powerstationsin k differentcitieswerebuil 查看详情
[vijos1011]滑雪
暴搜1#include<cstdio>2#include<iostream>3#include<cstring>4usingnamespacestd;56intnum[505][505];7intAns=1,n,m;8intfx[4]={0,0,1,-1};9intfy[4]={1,-1,0,0};1011voiddfs(intx,inty,intlen){12 查看详情
vijos2006
排列组合。递推式C(n,m)=C(n-1,m)+C(n-1,m-1)。容斥+前缀和记录一下即可，询问O（1）。#include<cstdio>#include<cctype>#include<algorithm>usingnamespacestd;intread(){charc;while(!isdigit(c=getchar()));intx=c-‘0‘;wh 查看详情
vijos1459车展
treap求中位数。#include<iostream>#include<cstdlib>#include<cstdio>usingnamespacestd;typedeflonglongll;intn,m,rot,siz,uu,vv;llh[1005],all,num,tmp,ans[1005][1005],cnt;structNode{intl,r,rnd, 查看详情
vijos1848记数问题
纯模拟能过...#include<cstdio>#include<cctype>#include<algorithm>usingnamespacestd;inlineintread(){charc;while(c=getchar(),!isdigit(c));intx=c-‘0‘;while(c=getchar(),isdigit(c))x=x*10+c-‘ 查看详情
p1004vijos
http://www.cnblogs.com/JerryZheng2005/articles/6685991.html1#include<iostream>2usingnamespacestd;34intn,m,a[21],b[21];5longlongf[21][201];67longlongmi(intx,inty)8{9longlongt=1;10for(inti=0;i< 查看详情
vijos1002过河
https://www.vijos.org/p/1002分析：很容易想到f[i]=min(f[i],f[i-j]+is_stone[i])的递推式，但L高达10^9，很明显会TLE，我们发现m<=100，在长达1到10^9的线段里就只有100个点这是多么的稀疏，我们看看有什么方法压缩一下，引用：问题的关键就... 查看详情
vijos1007绕钉子的长绳子
https://vijos.org/p/1007分析：刚开始没看到逆时针，后来发现是道sb题。。。长度=钉子周长+多边形周长#include<iostream>#include<cmath>#include<iomanip>usingnamespacestd;constintmaxn=110;constdoublepi=3.14159;doublex[maxn] 查看详情
vijos1097合并果子
手写了一发二叉堆。#include<cstdio>#include<cctype>#include<algorithm>usingnamespacestd;inlineintread(){charc;while(c=getchar(),!isdigit(c));intx=c-‘0‘;while(c=getchar(),isdigit(c))x=x*10+c- 查看详情