0824

rt #### P12624 [ICPC NAC 2025] Humans vs AI [题解](https://www.luogu.com.cn/article/tos6surv) #### P2900 [USACO08MAR] Land Acquisition G 斜率优化板子题，把没必要的区间删掉，然后就是 $x$ 递减 $y$ 单增的一些点了，然后朴素 `dp` 即可。 #### CF115E Linear Kingdom Races 线段树优化 dp，考虑先设计一个一维状态的 dp，$f_i$ 表示前 $i$ 个点考虑了的最大贡献，直接推一下式子，线段树优化即可。 #### AT_arc114_f [ARC114F] Permutation Division 思维题 首先 $a_1\le k$ 乱做不管 对于 $a_1>k$ 的，肯定是一段原来的加上后面乱选 原因显然？因为 $a_1>k$，那么无论怎么最优肯定a_1都是k了 不妨枚举这个长度，然后转为子问题 `solve(1,n) = `最优的 `a_1~a_l+solve(l+1,n,k-1)` 结束条件是 $k=0$ 不合法或者 $a_{l+1}\le k$ 然后乱选跳出去。 具体看代码。 #### P5391 [Cnoi2019] 青染之心 朴素 `dp` 复杂度 $qV$ 能过，但是空间也是 $qV$ 的。 考虑把这个建成一颗树的样子，然后每个点的值就是 $root$ 到这里的点随便选得到的。 考虑树链剖分后最多 $\log$ 条，也就是说最多同时开 $\log$ 个数组，用完清空掉后好了，空间 $V\log$，完美。 #### P4107 [HEOI2015] 兔子与樱花 小清新贪心题，直接考虑一层一层的看，因为看完接下来就不会再看了。 由于保证了初始状态合法，直接对于每个 $i$，将其儿子删掉后造成的贡献排序，然后一直删直到不能删即可。 注意到唯一受影响的就是 $i$，注意到如果**因为下面的**（即下面选了一些，而不是没选）选不了 $i$，那么会使下面的少选至少一个，而这里选的贡献是 $1$，显然不换答案不会更劣，然后没了，复杂度 $n\log n$，瓶颈在于排序。 话说如果删除一个点造成的代价不一样会怎么样捏，感觉就不太好搞了。