简单 DP

总结暑假的 DP 小练习

A

有一排 n 个电线杆, 第 i 个的高度为 。要在相邻的电线杆间造电线。每一根的代价是 。为一根电线杆增加 x 高度的代价是 , 最小化代价和。 .

暴力 DP, 表示前 i 个电线杆,其中第 i 个电线杆高度为 j 时的最小代价。

时间复杂度 . 把绝对值拆开,变成两个决策集合:

前半部分可预处理前后缀的 ,做到 查询。后半部分 计算。时间复杂度 .

B

给出一个长度为 的序列 。对于每个 , 判断是否存在

FWT 解释成状圧……全靠口糊

C

给出一张 个点 条边的图,求一个人从 点出发经过所有点恰好一次的路径方案数。

一个哈密尔顿通路。但是要注意这道题有重边。所以记录重边的数量变成简单图,这样在计数的时侯乘一下就行。

D

给出 个子串, 要求构造一个序列包含所有这 个子串,求最小长度。

显然,序列一定以某个子串结尾。首先把包含关系的子串踢掉,然后 表示序列以第 i 个子串结尾,匹配子串集合的状态是 j 的最小长度。转移的时侯暴力,后缀数组,hash 都能干吧。

E

个整数排成一列,问前缀和不出现给定的 个数 的方案数。

表示选择的数的集合状态是 i 的方案数。由于有了选择的状态,可以直接算总和,就能转移了。

F

CF895C

给出 个数,问有多少个非空子集的乘积为完全平方数。

先来一个左队的方法吧。注意到 ,在 9 以内的质数只有 2,3,5,7,于是我们把一个数分解质因数,用一个二元组 表示这个数。其中 S 表示 2,3,5,7 的次数的奇偶性。因为我们只关心能否形成完全平方数,因此关注奇偶性即可。而 x 表示剩下的大于 的质因子。

显然我们想让 x 也出现奇数次,于是我们把二元组按 x 排序,这样就可以顺着 DP 了。假设有 k 个不同的 x 构成序列 ,那么思路大概是 表示考虑前 i 个不同的 x,其中 选择了 j 个,并且保证 选择的次数是偶数次,并且 2,3,5,7 的状态为 S 的方案数。显然可以通过选择当前的二元组转移到 。而 可以转移到 。于是貌似在做的过程中可以不要 j 这一维,转移的时侯是 0D 的,所以复杂度大概是

当然这道题也有线性基的做法,但本人太菜不会就不讲了


  转载请注明: Sshwy's Blog 简单 DP

 上一篇
UVA437The Tower of Babylon UVA437The Tower of Babylon
UVA437The Tower of Babylon你可能已经听说过巴比伦塔的传说。现在这个传说的许多细节已经被遗忘。所以本着本场比赛的教育性质,我们现在会告诉你整个传说: 巴比伦人有 n 种长方形方块,每种有无限个,第 i 种方块的三边边
2018.10.01
下一篇 
BZOJ4010:[HNOI2015] 菜肴制作 BZOJ4010:[HNOI2015] 菜肴制作
题面 错误原因难得遇到一道题让我写错误原因。。。 错解 首先,这道题不是字典序最小,因为他从 1,2…n 依次考虑。 一开始想直接贪心遍历,从 1 号考虑,为了做 1 号,就要把它的先决菜肴都做了,于是先做价值高的先决菜肴再做第二高的,这样
2018.10.01
  目录