DP

· · 个人记录

明明 DP 就差确很晚才总结。

树形 DP

DYN-Dynamite

最小点覆盖问题。但是我太菜只会距离为 2 以内的,此类还可以改动态 DP，不做赘述。

说这个题，显然二分，然后树形 DP。考虑一些类似贪心的思想。如果以一个子树的根节点为根，到所有子树中的关键节点最远的距离小于等于当前的 mid，那显然目前来说选这个跟最优，但是在往上走的过程中，如果某一个根节点够不到所有关键子孙，就需要在子孙中选其他的点来保证覆盖，此时应该选谁呢。

我们考虑把刚才那个步骤优化，一个子树，当根节点到子孙中最远关键节点，正好等于 mid 时，就选用这个节点，并且在往上走时，更新它能同时覆盖的其他节点。然后告诉父亲哪些点覆盖不到，维护出每个节点当前最远的没有覆盖的关键子孙，一起类推继续往上推即可。根节点特判。

总结一下交了好几遍都没过的原因。我只用了一个数组来记录信息。用正负来区分是能继续覆盖还是需要覆盖。但是当 dp 值是 0 的时候不知道这个节点本身有没有被覆盖。所以还得加个布尔判断一下是哪种状态。

无可奈何花落去

本以为是期望 DP，但是想了半天发现期望不好累积起来维护，原来是树上背包。

我忘掉了一个很重要的结论，link。

但是要注意写法的正确性，DP 中 siz 加一个子树更新一次，不然就假了。

至于这题 DP 本身就很简单了，设一个三维状态 f[i][j][k] 表示在子树 i 里选 j 个边断掉 i 的状态为 k 使它凋零有多少种情况，然后转移一下就行了。

【MX-S1-T3】电动力学

好题。借这个题复习一下圆方树，把每个点双里的点通过一个方点相连，然后形成一个最多 2n 个点的方圆相间的树，通过巧妙地设置点权可以解决许多问题。

具体建树方法：tarjan 的时候，对于一个节点 u，每找到一个儿子 v，满足 low[v]==dfn[u]，就把栈顶部若干个提取出来，注意只提取到这个儿子，无向图重边要注意特判。

DP 好难。好难。不会。

状态设计很巧妙，乘法原理，很深刻。

贴一下 xieziheng 的 题解，写得好。

期望 DP

Revenge of The Salary

打 ABC 时的题，倒不是有多难。我没写过也不会这种期望之类的 DP。用这道题学一下。这种题的套路大致都是求每个数字对答案产生的贡献。

这个题也许还是比较简单了。设每个数被选到的概率是 p_i，那么就有 p_i=\sum_{j=0}^{i-1}p_j\times \frac 1 n ，其中 p_0=1，于是就做完了。

聪聪与可可

简单题。一开始没想明白怎么更新状态，差点想写记忆搜，但是发现方向有问题。其实就是根据距离 DP 就行了。

我们发现每次经过两人每操作一回合两人距离都会更进一步。所以直接从小到大枚举两点间的距离 DP 就行了，DP 复杂度 n^2，不过好像还得套个全源最短路，边权都是 1，直接 BFS，还是 n^2，这个弱智题写完才发现忽略走路花费时间，是聪聪先走。

区间 DP

Greedy Pie Eaters P

DP 状态的设计是好巧妙。设奶牛吃掉 [i,j] 范围内的派能获得的最大体重是 f[i][j]，注意吃掉这个区间不能超过 [i,j] 的范围，然后就有了 f[i][j]=max_{k< i< j}(f[i][k-1]+f[k+1][j]+g[i][j][k])，我们设这个区间最后一个被吃掉的派是第 k 个派，那么能获得的最大价值就是左边的的加右边的（它们由于 f 的定义一定不会吃掉 k），然后再在这个区间中取一个左右端点在 [i,j] 之间并且包含 k 的体重最大的奶牛来吃这个派，而 g 函数的更新方式也很容易，g[i][j][k]=max(g[i][j-1][k],g[i+1][j][k])，再和左右端点正好是 i 和 j 的那个奶牛体重取 max。

感觉这种题最巧妙的还是状态设计的时候的限制条件，很好地使这个问题能够 DP 起来了。

Outer space invaders

首先时间和距离都可以离散到 n 的级别，而 n\le 300，允许我们使用三次方的算法，区间 DP。但是我还是不会。

我好蠢啊啊啊。

还是巧妙在设计状态的限制上。

设 f[i][j] 表示消灭左右端点都在 [i,j] 以内的敌人的最小代价，这样我们在枚举中间点 k 的时候就可以保证 f[i][k] 的敌人一定不可能拖到 k 之后再被消灭，让两个区间彻底分开。

然后还需要一些贪心的东西，这题太妙了。。

我们考虑左右端点都在 [i,j] 区间的距离最远的那个敌人，首先他一定要被消灭，假如我么在 t 时刻消灭他，那么 t 时刻存在的所有左右端点在 [i.j] 的敌人都会被消灭。于是我们直接枚举这个 t 时刻，因为左右端点跨过 t 的一定会被消灭，而没跨过 t 的一定不会被消灭，所以就直接拿另外两半的 f 函数更新就好了！

状压 DP

我本来以为状压都是一些很板子的弱智题。

愤怒的小鸟

想了一段时间，只会 Tn^22^n 的做法。感觉 O(10^9) 不太像正解。看了一眼题解，妙！

由于三点确定一个抛物线，已给原点，所以 n 个点最多确定 n^2 个抛物线，因此用这 n^2 种抛物线能涵盖的点做为状态转移即可，这就是 Tn^22^n 的做法。

但是有一个很聪明的点。其实我之前考虑过，但是这题忘了。

算是状压转移的时候的一个 trick 吧。你可以只考虑和其中某一位 1 相关的转移。比如现在要更新 f[x] 的状态，设 i=lowbit(x)，那么 f[x] 一定可以由某一种和 i 相关的状态转移而来，而和 i 相关最多 n-1 条抛物线。因此复杂度下降到了 Tn2^n！

Minimum Sum of Maximums

呃呃。我竟然不会枚举子集的 trick。可能几年前刚学的时候遇到过吧，反正现在忘了。

简单记一下。

for(int j=i;j;j=i&(j-1))

这个枚举保证枚举出来的 j 是单调递减的，不重不漏。

你单次枚举一个集合的子集肯定是 2^{|T|}的。但是对于一个集合 s 枚举它所有子集的子集总复杂度只有 3^{|S|}，二项式定理易得。

然后是这个题。状压 DP 套区间 DP。

其实好像也不是特别难。

分析性质，每一段的贡献最优可以做到 Max-Min。然后把 a 排个序，对着 k+1 个区间做状压再套一个区间 DP 就好了。

wqs 二分

放到 DP 这里吧。一般来说严格证明一个 dp 问题是凸的都是用费用流建模的方法。但是实际上好像有很多问题都是凸的，可以猜（或打表）。

凸函数大概就是随着选择的数的增加，每增加一个选的数，带来的效果会越来越小。

wqs 二分一般用于一些限制选的个数的 dp，不限制个数的时候很好做，但是限制后是一个凸函数的问题。

阿粲给了我一个理解二分斜率的角度，就是说二分一个代价，然后随着选的数的个数的增长，这个代价会形成一个一次函数，此时的 dp 值就是原来的凸函数减去一个一次函数，只有与这个代价也就是斜率相切的点的函数值最大。

然后需要区分两种情况，一种是限制选 m 个以内，一种是限制必须选 m 个，选 m 个以内的它一定是前 m 个的最优解，只需要找到满足在前 m 个且斜率最小的点，而必须选 m 个则是找到第 m 个点的切线斜率，另外注意一条切线上有多个点，一般上凸都是找最后一个点。

很多费用流模型还可以用反悔贪心来做，也可以看做是模拟求增广路。