Posts tagged with DP


AC自动机+带权字符串DP 题目本身不是很难,但在处理上有点繁琐。 题意: 给你很多模式串,每个模式串都有一个权值,再给你一个限制长度,要你在限制长度内找出最短的字符串,使得权值和最大。若有多个结果,输出字典序最小的。 思路: 连AC自动机上的最短路都有了,加个权值也不是什么奇怪的事情。 这个加了权值有点像…………背包??不是么?? 想象不到的话将背包的物品替换成一个字符试试。 但是实际上都是我瞎猜罢了,我并没有按照背包的写法去写,还是很常规的按照节点和状态添加字符,到下一节点的下一状态。 稍微繁琐一点的就是要输出字符串,但所幸数据比较小,…

AC自动机+spfa最短路 啊啊,明明AC自动机还有最后一题,今晚怕是写不完了,今天写的还有两道没写题解。 最后一道AC自动机与这一题有相似之处,是这一题的强力加强版本。 先把这题给解决了 题意: 给你很多碱基串,不同碱基串在前后缀相同的条件下可以重叠,要你求出最短的碱基串,包含所有给定串。 思路: AC自动机上状压SPFA,也可考虑TSP的模型。 还是属于比较基础的,连我都可以不看题解写出来的题目。 #include <cstring> #include <…

AC自动机 + 变进制状压DP 看题目的 discuss 都说会卡数据,但我还是 1500ms A了。虽然变进制的思路并不是我的…… 最近有点懒得写博客了呀 题意: 还是基因碱基对背景。 给你几个模式串,再给你一个匹配串,允许你对匹配串重新排列,要求重新排列后跟模式串匹配的最大数量。 思路: 如果再加个权值,那就是DP套DP了,(误…… 本质上还是一个计数DP,考虑状压,但是给定的匹配串长度上限为 40 ,如果开一个状态+…

训练赛的DP套DP,关于DP套DP,以前记得好像做过一道。题目本身十分巧妙,但貌似不是很多。可能不是很好出题吧。 所谓DP套DP,就是我DP所需的状态也需要额外的DP求出来。简单说,就是我需要DP两次,在第一次的DP结果上再DP一次。 题意: 给你一个DNA序列,再给你一个固定长度,问你在这个长度下的所有序列中,与给定的DNA序列的LCS分别为( [0,len(DNA)] )的序列数量。 思路: 因为数据很小,我们可以考虑用状压做。 对于当前长度的一个最优状态,如果增加一个字符,…

CLS的状压DP系列…… 然而实际上也算是一道简单题,但是我并没有立刻写出来。 不知道为什么,每次我尝试这用已知最优状态去推其他状态都是错的…… 然而用当前状态之前的状态来推当前状态却是对的。 顺便学习了一个,二进制子集的枚举方法。for ( int sta = state ; sta ; sta = (sta - 1) & state ) 学了这么久状压居然连这个都知道真是醉了…… 题意: 给你一个字符串,每次只能取走一个回文串,问最少取几次。 思路:…