http://www.luogu.org/problem/show?pid=2679
题目描述
有两个仅包含小写英文字母的字符串 A 和 B。现在要从字符串 A 中取出 k 个互不重叠的非空子串,然后把这 k 个子串按照其在字符串 A 中出现的顺序依次连接起来得到一 个新的字符串,请问有多少种方案可以使得这个新串与字符串 B 相等?注意:子串取出 的位置不同也认为是不同的方案。
输入输出格式
输入格式:
输入文件名为 substring.in。
第一行是三个正整数 n,m,k,分别表示字符串 A 的长度,字符串 B 的长度,以及问
题描述中所提到的 k,每两个整数之间用一个空格隔开。 第二行包含一个长度为 n 的字符串,表示字符串 A。 第三行包含一个长度为 m 的字符串,表示字符串 B。
输出格式:
输出文件名为 substring.out。 输出共一行,包含一个整数,表示所求方案数。由于答案可能很大,所以这里要求[b]输出答案对 1,000,000,007 取模的结果。[/b]
输入输出样例
6 3 1
aabaab
aab
2
6 3 2
aabaab
aab
7
6 3 3
aabaab
aab
7
说明
对于第 1 组数据:1≤n≤500,1≤m≤50,k=1;
对于第 2 组至第 3 组数据:1≤n≤500,1≤m≤50,k=2; 对于第 4 组至第 5 组数据:1≤n≤500,1≤m≤50,k=m; 对于第 1 组至第 7 组数据:1≤n≤500,1≤m≤50,1≤k≤m; 对于第 1 组至第 9 组数据:1≤n≤1000,1≤m≤100,1≤k≤m; 对于所有 10 组数据:1≤n≤1000,1≤m≤200,1≤k≤m。
【题目分析】
用了两个状态转移方程(f[i][j][l][0]表示到A串第i个字符B串第j个字符为止用l个子串A串中前i个元素组成B串前j个元素的方案总数,f[i][j][l][1]表示以A串第i个字符结尾的方案总数)。状态转移方程见代码,总体思想就是当a[i-1]==b[j-1]时,本次转移可以转移到f[i-1][j-1]l。最后就是显然i都是i-1转移来的,因此可以滚动数组优化
#include <cstdio>
using namespace std;
char a[],b[];
long long f[][][]={};
int n,m,k;
int main()
{
scanf("%d%d%d",&n,&m,&k);
scanf("%s%s",a+,b+);
for(int i=;i<=n;i++)
for(int j=m;j>=;j--)
for(int l=;l<=k;l++)
{
if(a[i]==b[j])
{
if(j==&&l==)
f[j][l][]++,f[j][l][]=;
else
{
f[j][l][]+=f[j-][l-][];
f[j][l][]=f[j-][l-][];
if(i>&&a[i-]==b[j-])
f[j][l][]+=f[j-][l][],
f[j][l][]+=f[j-][l][];
}
}
else f[j][l][]=;
f[j][l][]%=;
f[j][l][]%=;
}
printf("%lld",f[m][k][]);
return ;
}
P2679 子串的更多相关文章
-
洛谷 P2679 子串 解题报告
P2679 子串 题目描述 有两个仅包含小写英文字母的字符串\(A\)和\(B\). 现在要从字符串\(A\)中取出\(k\)个互不重叠的非空子串,然后把这\(k\)个子串按照其在字符串\(A\)中出 ...
-
P2679 子串 DP
P2679 子串 DP 从字符串A中取出\(k\)段子串,按原顺序拼接,问存在多少个方案使拼接的字符串与字符串B相同 淦,又是这种字符串dp 设状态\(ans[i][j][k]\)表示A串位置\(i\ ...
-
Luogu P2679 子串(字符串+dp)
P2679 子串 题意 题目描述 有两个仅包含小写英文字母的字符串\(A\)和\(B\). 现在要从字符串\(A\)中取出\(k\)个互不重叠的非空子串,然后把这\(k\)个子串按照其在字符串\(A\ ...
-
[NOIP2015] 提高组 洛谷P2679 子串
题目背景 无 题目描述 有两个仅包含小写英文字母的字符串 A 和 B.现在要从字符串 A 中取出 k 个互不重叠的非空子串,然后把这 k 个子串按照其在字符串 A 中出现的顺序依次连接起来得到一 个新 ...
-
[LUOGU] P2679 子串
一开始用一个f数组转移,发现不太对,状态有重叠部分 f[i][j][k]表示考虑了s的前i位,匹配到t的第j位,用了k个子串,且s的第i位必选 g[i][j][k]表示考虑了s的前i位,匹配到t的第j ...
-
洛谷P2679 子串——DP
题目:https://www.luogu.org/problemnew/show/P2679 DP水题: 然而被摆了一道,下面加 // 的地方都是一开始没写好的地方...还是不周密: 仔细审题啊... ...
-
洛谷 P2679 子串
题目背景 无 题目描述 有两个仅包含小写英文字母的字符串 A 和 B.现在要从字符串 A 中取出 k 个互不重叠的非空子串,然后把这 k 个子串按照其在字符串 A 中出现的顺序依次连接起来得到一 个新 ...
-
2018.11.04 洛谷P2679 子串(线性dp)
传送门 为什么前几年的noipnoipnoip总是出这种送分题啊? 这个直接线性dpdpdp不就完了吗? f[i][j][k][0/1]f[i][j][k][0/1]f[i][j][k][0/1]表示 ...
-
洛谷P2679 子串 [noip2015] dp
正解:dp 解题报告: 感觉是道dp好题啊,所以就写了个题解 代码实现难度低,思维难度大,像我这种思维僵化傻逼选手只想到了爆搜+组合数学... 其实是道很妙的dp题!好趴也没有多妙主要大概是妙在想到了 ...
随机推荐
-
java集合-LinkedList
一.概述 LinkedList 与 ArrayList 一样实现 List 接口,只是 ArrayList 是 List 接口的大小可变数组的实现,LinkedList 是 List 接口链表的实现. ...
-
oracle 日期获取
,'YYYY-MM-DD')星期一, to_char(NEXT_DAy(to_date(,'YYYY-MM-DD')星期日 from dual; select to_char(sysdate,'yyy ...
-
TCP/IP Four Layer Protocol Format Learning
相关学习资料 tcp-ip详解卷1:协议.pdf 目录 . 引言 . 应用层 . 传输层 . 网络层 0. 引言 协议中的网络字节序问题 在学习协议格式之前,有一点必须明白,否则我们在观察抓包数据的时 ...
-
《Entity Framework 6 Recipes》中文翻译——第十章EntityFramework存储过程处理(八)
将插入.更新和删除操作映射到存储过程 问题 您想在存储过程中映射插入.更新和删除操作. 解决方案 下图所示的运动员Athlete实体模型.底层数据库有一张运动员Athlete表.您想使用存储过程进行实 ...
-
【转载】 spring事物配置,声明式事务管理和基于@Transactional注解的使用
https://blog.csdn.net/bao19901210/article/details/41724355
-
教你用Python创建瀑布图
介绍 对于绘制某些类型的数据来说,瀑布图是一种十分有用的工具.不足为奇的是,我们可以使用Pandas和matplotlib创建一个可重复的瀑布图. 在往下进行之前,我想先告诉大家我指代的是哪种类型的图 ...
-
【枚举】【贪心】Codeforces Round #482 (Div. 2) B. Treasure Hunt
题意:给你3个字符串,3个人各对自己的字符串执行n轮操作,每一次选择一个字符变为任意一个和原来不同的字符.最后问你谁能使自己的串中的任意重复子串出现的次数最大化. 显然只需关注字符而非子串. 枚举每个 ...
-
Qt Creater中Clang-format的使用
起因在于习惯性的想格式化代码,发现Qt Creater默认居然是没有代码格式化的,只有一个缩进,搞毛线啊!!! 搜索了下,倒是很容易就搜到了,Qt Creater中有个插件:beautifier,在 ...
-
利用Tensorflow进行自然语言处理(NLP)系列之一Word2Vec
同步笔者CSDN博客(https://blog.csdn.net/qq_37608890/article/details/81513882). 一.概述 本文将要讨论NLP的一个重要话题:Word2V ...
-
内功心法 -- java.util.LinkedList<;E>; (5)
写在前面的话:读书破万卷,编码如有神--------------------------------------------------------------------下文主要对java.util ...