NFLS Dp 12.14

wgyhm

2024-01-03

NFLS, dp, 小结, 笛卡尔树

来源于 12.14 dp 训练。

如果没自己做出来会打星号。

暂时还没有补完。——last update 2024.1.3

简单 dp

我也不知道什么标题。

[AGC034E] Complete Compress

https://www.luogu.com.cn/problem/AT_agc034_e

枚举根 $r$。记 $x$ 为 $r$ 的儿子。$d_x$ 为所有有标记的点到 $x$ 的距离，记 $sum=\sum d_x$。如果 $\exists x,2d_x\le sum$，则能全部消掉，否则消不掉。

观察到如果一个子树内消消到的距离最小值为 $g_x$，最大值也就是不消的距离和为 $f_x$。则 $g_x,f_x$ 奇偶性相同且对于奇偶性相同的在 $[g_x,f_x]$ 的距离都可以构造出来。于是我们想求出 $g_x$。

考虑从儿子中转移。我们贪心的想使得 $f_x$ 最大的先在子树内消一下，然后再和其他的儿子一起消。如果 $\exists x,g_x+siz_x\le sum-(f_x+sum)$，则 $g_r=f_r\bmod 2$，否则 $g_r=g_x+siz_x-sum+f_x+suz_x$。

如果为 $r$ 根合法当且仅当 $g_r=0$。复杂度 $O(n^2)$。

*CF908G New Year and Original Order

记数的位数为 $n$。

先讲一下自己想到的 $O(10^2n^2)$ 做法。

和 link 一样，将排序以后的数看成若干个 $111\dots 111$ 构成的后缀。

而在本题中，记 $f(k,i)$ 表示 $k$ 在所有数中恰好出现在第 $i$ 位的个数，答案为 $\sum k\sum _{i=1}^n 10^{i-1}f(k,i)$。而恰好不好算，考虑一个很经典的竖着算转横着算，计算 $f(k,i)$ 表示 $\ge k$ 的数在所有数中恰好出现在 $i$ 次的个数，答案为 $\sum k \sum _{i=1}^n f(k,i)\times w(i)$，其中 $w_i=111\dots 1$，总共 $i$ 个 $1$。前面那个东西再记个是否顶到上界。应该好 dp。

然后看题解的 $O(10^2n)$ 的算贡献做法感觉很高妙啊。

考虑对每一个数 $d$ 算贡献。记 $f(i,0/1)$ 表示算到第 $i$ 位，数 $d$ 对答案的贡献。$g(i,0/1)$ 表示算到第 $i$ 位，在第 $i$ 位放 $d$ 对答案的贡献。后面的 $0/1$ 表示是否顶到上界。

然后枚举 $i-1$ 位的数位 $x$。有转移：

$x<d$，那么 $f(i,0/1)\gets f(i-1,0/1),g(i,0/1)\gets g(i-1,0/1)$。
$x=d$，那么 $f(i,0/1)\gets 10f(i-1,0/1)+g(i-1,0/1),g(i,0)\gets g(i-1,0/1)$。
$x>d$，那么 $f(i,0/1)\gets 10f(i-1,0/1),g(i-1,0/1)\gets 10g(i-1,0/1)$。

分别就是看加入一个数对前面是否左移。

*CTT2017 某位歌姬的故事

https://www.luogu.com.cn/problem/P4229

先把区间离散化，这样只有 $2q$ 个点。

区间 $\max$ 为一个数，等价于区间所有数都小于等于 $\max$，且存在一个数等于 $\max$。

先对每个操作做区间覆盖，则每个点有一个取值上限 $h_i$。

对于每个点，只可能对 $\max=h_i$ 的区间有贡献。考虑把对于每个值把这样的区间拿出来。问题转化为了一个序列，染黑（存在 $h_i$）或者染白，有许多区间限制，每个区间中至少要有一个染黑的，求方案数。

先转化为所有都染白，然后有些点染黑的方案数。令 $f_i$ 表示钦定 $i$ 为结尾且染黑的方案数，再维护一个左端点表示可以转移的区间，再前缀和搞搞就好了。

复杂度 $O(q\log q)$。

加强版：https://www.luogu.com.cn/problem/AT_abc262_h。

笛卡尔树 dp

结合笛卡尔树做 dp。

BZOJ4380 [POI2015] Myjnie

https://www.luogu.com.cn/problem/P3592

观察到只有 $m$ 个有用的取值，先对 $c_i$ 离散化。

考虑区间 dp。令 $f_{l,r,k}$ 表示区间 ${l,r}$，最小值为 $k$ 的价值最大值。

转移枚举最小值所在的位置，算贡献预处理后缀和和 dp 数组的后缀最大值。

复杂度 $O(n^3m)$，有 $1/6$ 的区间 dp 常数，可以通过。

可以理解成把序列构成了一颗笛卡尔树，并且考虑在笛卡尔树上计算贡献。

BZOJ2616 PERIODNI

https://www.luogu.com.cn/problem/P6453

观察到小的会影响大的而大的超出的部分不会影响小的，把序列做一个小根笛卡尔树。

令 $f_{i,j}$ 表示在子树 $i$ 中，已经选了 $j$ 个互不攻击的点的方案数。先把儿子的答案合并。

然后考虑在点 $i$ 的区间选，也就是宽为 $h_i-h_{fa_i}$，长为 $siz_i$ 的矩形选 $k$ 个点转移。对每个 $f_{i,j}$ 转移即可。

复杂度 $O(n^3)$。实现的好的话跑不满。

[AGC026D] Histogram Coloring

写了一个 $O(n^3)$ 的 dp。后面发现好像可以 $O(n)-O(n\log n)$。具体用小根笛卡尔树，然后计算一个矩形染色的方案数。讨论一些情况。

[JOI Open 2016] 摩天大楼

插入 dp。同 ZJOI 波浪。

考虑一个把所有元素按照从大到小的顺序放到排列中正确的位置的过程。那么每次插入一个元素，其所在的连续段就是以其为根在笛卡尔树上的子树。

这么做最后的值域会很小，但是 dp 中存在加减用到的值域会很大。考虑将 dp 差分，这样每次都是加法。

细节比较多。

dp 套 dp

dp 套 dp 是给定一个 DP 问题 A，用另一个 dp 去计算一种可能的 A 的输入，使得 A 的 dp 结果为 $x$。

也就是外层的 dp 的状态是另一个 dp 的结果。

BZOJ3864 Hero meet devil

https://hydro.ac/d/bzoj/p/3864

经典 dp 套 dp。先考虑求 LCS 的 dp。设 $f_{i,j}$ 表示 $t$ 的前 $i$ 位和 $s$ 的前 $j$ 位的 LCS。

然后把这个第二维状态记录下来。设 $F_{i,S}$ 表示当前考虑 $t$ 的前 $i$ 位，$f_i$ 的状态是 $S$ 的方案数。

第二维状态看上去是 $|s|^{|s|}$ ，分析发现相邻两个数的值最多只会差 $0/1$，状态存其 dp 值的差分数组即可优化为 $2^{|s|}$。状态与状态之间转移预处理出来即可 $O(1)$ 转移。

dp 复杂度 $O(m2^n)$。