ZROI2018.8.4 简单 DP

总结暑假的DP小练习

Exercise 1

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

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

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

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

Exercise 2

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

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

Exercise 3

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

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

Exercise 4

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

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

Exercise 5

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

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

Exercise 6

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 ZROI2018.8.4 简单 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
  目录