笔记 2023.12.16：动态规划

今天题目很多，可能有些题不口胡了。

LOJ6089 小 Y 的背包计数问题

前 \(\sqrt n\) 个物品直接做单调队列优化是 \(O(n\sqrt n)\)。

大于 \(\sqrt n\) 的是完全背包。考虑到完全背包 \(v\) 的 OGF 为 \(\dfrac{1}{1-x^{v}}\)。这不行。

你考虑到对于一个物品序列，一个物品可以看作是先加入 \(\sqrt n\)，然后不断加一。对于一个序列，就是加入 \(\sqrt n\) 和 \(+1\) 不断进行，不需要交错，所以 \(f_{i,j}\) 表示放进去 \(i\leq \sqrt n\) 个物品，\(j\) 是总体积，那么 \(f_{i,j}=f_{i-1, j-\sqrt n}+f_{i, j-i}\)。\(O(n\sqrt n)\)。

两边的背包可以轻易合并到 \(n\)。

总结：可以改变状态定义，尤其是根号分治的时候把小的一维扔进去，这里就是物品数量 \(\leq \sqrt n\)。

LOJ3776 Uplifting Excursion

一开始暴力加入所有负数，然后从小到大加入正数，直到 \(>L\)；如果整个都选了，删除绝对值最大的负数，如果还是 \(\leq L\) 直接无解跑路。现在重量 \(W\in[L, L+m)\)。考虑进行调整。

调整就是删除一些数字，加入一些数字，观察到你可以通过调整调整的顺序使得 \(W\in[L-m, L+m]\)。非常简单，\(W<0\) 就做加的，\(W>0\) 就做减的，因为它们的绝对值 \(\leq m\)。
如果 \(W\) 两次到达同一个地方，说明中间跨过这些数字都是无用的，可以删掉，于是认为 \(W\) 只会在 \([L-m, L+m]\) 之间横跳且不会重复。\(\implies\) 物品数量 \(\leq 2m+1\)。
所以我们对加入和删除的物品，直接 dp 到容积 \([-2m^2, 2m^2]\) 即可。\(O(m^3)\)。

P5336 [THUSC2016] 成绩单

\(f_{l, r}\) 表示删完区间 \([l, r]\) 的答案，\(g_{l, r, mn, mx}\) 用于辅助求 \(f\)，转移分为 \(r+1\) 是归进最外面一层还是在里面删除。

*AGC035D Add and Remove

\(a_1, a_n\) 是删不掉的。考虑最后一次删了 \(a_x\)，那么就是说答案是 \(a_1+a_n+2a_x\) 注意这个 \(2\) 很关键。我们定义神秘的状态 \(f(l, r, fl, fr)\) 表示 \(l-1\) 最终会以神秘姿态翻个 \(fl\) 倍计入答案，我不知道它是怎么算的，但是我要求是 \([l, r]\) 删完以后你要把贡献打在 \(l-1\) 上；\(r+1\) 会翻 \(fr\) 倍，我同样不知道它是怎么做到的，但是你要使得最终答案最小。这样就可以算：

\[f(l, r, *, *)=\sum_kf(l, k - 1, *, *)+f(k+1, r, *, *)+a_k\times\circ \]

其中 \(*, \circ\) 我待定系数，仔细考察一下系数啊，这里

*AGC039E Pairing Points

CF1517F Reunion

枚举答案 \(< r\)，意思是黑点距离 \(r\) 以内必有一个白点，考虑树形 DP，点 \(u\) 所在子树内最浅的白点和最深的黑点的深度都记下，然后可以合并。考虑到子树内如果黑点已经覆盖完了就不用记黑点，否则这个白点没有覆盖掉最深的黑点，覆盖最深黑点的白点在外面，此时它已经劣了，向上走没用。所以只需要记一个。\(O(n^3)\)。

*AGC034E Complete Compress

我觉得需要补个题解

P7897 [Ynoi2006] spxmcq

\[f_u=a_u+x+\sum_{v\in son(u)}\max(f_v, 0) \]

\(\max(\circ, 0)\) 太草，考虑一个森林，初始时全是独立点，随着 \(x\) 增长，\(f_u\) 增长，当 \(f_u>0\) 时加入 \(u\to fa_u\) 的边。然后写成：

\[f_u=a_u+x+\sum_{v\in son(u)} f_v=\sum_{v\in subtree(u)}a_v+x\sum_{v\in subtree(u)}1 \]

也就是 \(f_u=sum_u+xsiz_u\)。随着 \(x\) 的增长，当 \(sum_u+xsiz_u>0\implies x>-\frac{sum_u}{siz_u}\) 时它就加边，加边的时候用并查集打通他到当前连通块的根的路径，然后做链加，在根上修改这个阈值，用任意数据结构维护新的阈值。