网站建设与管理专业好不好就业,国内最大的网站建设公司排名,扁平化设计网站,青海网页设计与网站建设dp套dp
这是一个对于一类动态规划的计数问题的处理方法#xff0c;问题常常是如果形式确定就可以直接dp#xff0c;但是现在却要求满足某个要求的所有方案数#xff0c;一般的处理方法就是一维负责增量构造#xff0c;其他维度用来表示内部dp状态#xff0c;然后转移时候…dp套dp
这是一个对于一类动态规划的计数问题的处理方法问题常常是如果形式确定就可以直接dp但是现在却要求满足某个要求的所有方案数一般的处理方法就是一维负责增量构造其他维度用来表示内部dp状态然后转移时候先让内部状态转移然后外部dp对应存储方案数。
类似于将内部的dp转移变成一个自动机可以接受所有不同的转移然后我们的外层dp就是在自动机上进行计数。
P4590 [TJOI2018]游园会
给定一个长度为k的字符串求解长度为n的字符串中LCS为i的个数对所有的i输出答案。
首先对于LCS的一般处理就是dp但是这里我们需要处理不同的串而不是单一的串的问题所以我们使用dp套dp然后对于内层状态我们需要保存不同串下的对应dp状态那么可以发现利用差分可以得到一个长度为k的01串那么我们可以将其视作是自动机的状态然后每次新增加一个字符就可以转移然后我们只需要在外层再套上一个dp来计数即可。
CF979E Kuro and Topological Parity
https://www.cnblogs.com/wmrv587/p/9051201.html 题意 给定n个点每个点有黑白两种颜色如果没有颜色那么你可以把它任意涂成黑色或白色同时你可以在这个图上任意加入一些边当然不能加入重边或自环要求加入的边必须从编号小的点指向编号大的点
我们称一条好的路径为经过的点为黑白相间的路径如果一个图好的路径的总数%2p那么我们称这个图为好的图现在给定你n个点的情况求这n个点能组成的好的图的个数答案取模10^97
首先如果图是一定的那么我们可以轻易的进行dp得到答案但是现在问题是图不是一定的所以我们就需要dp套dp解决因为我们只关注路径个数的奇偶性所以状态只需要保留终止点为黑色和白色的点数的奇偶性因为其它点都是可连可不连的然后只需要一个颜色不同有奇数个链的点存在那么最后结果是奇数和偶数的方案都是2i−22^{i-2}2i−2,所以这样我们就可以做到O(n)的复杂度了。
