感觉自己 dp 不行，打算先专门练一阵子 dp。
以下是从国庆开始的训练实录。
会根据我自己水平定个难度。
- \(\rm Easy\)：独立想出并用时短。
- \(\rm Middle\)：独立想出并用时长。
- \(\rm Hard\)：看了题解，理解用时短。
- \(\rm VeryHard\)：看了题解，理解用时长。
20221001
- 【NOI2016】国王饮水记（\(\rm VeryHard\)）
牛逼的找结论 dp 题。
20221005
- [AGC013D] Piling Up（\(\rm Middle\)）
有意思的格路计数。不过直接 dp 即可通过。
20221006
- CF868F Yet Another Minimization Problem（\(\rm Easy\)）
有趣的决策单调性优化 dp，要莫队计算贡献。
20221008
- [TJOI2019] 甲苯先生的线段树（\(\rm VeryHard\)）
有一车天上掉下来的结论的数位 dp。
对结论的口胡证明放在本地。 - [THUPC2021] 混乱邪恶（\(\rm Hard\)）
神秘的背包 dp，要随机顺序转移来优化状态，这个结论好神秘哇……
20221009
- CF1392H ZS Shuffles Cards（\(\rm Middle\)）
推柿子的 dp。
My Solution。
20221010
- [HNOI2008] Cards（\(\rm Easy\)）
Burnside 引理，再加上简单背包计算即可。 - [SDOI2009] 学校食堂（\(\rm Easy\)）
简单状压。细节有点多。 - [SHOI2009] 舞会（\(\rm Hard\)）
为啥要出高精度。
打了个 \(O(n^4)\) 的暴力（算上高精度用时）过了，看了看耗时发现不对劲。（好吧其实我是加了一车剪枝的压位高精）
好家伙，为啥这题 \(O(n^4)\) 都能草啊。
看了题解才发现正解是 \(O(n^3)\) 的。
这种双射技巧好牛逼啊。不过蛮好理解的。
然后不看题解自己推，推了巨久还推挂几次，最后画了个图才解决。
然后通过压位高精跑到了最优解。 - [USACO15JAN] Moovie Mooving G（\(\rm Easy\)）
小丑表示自己没看到是从 \(0\) 开始的 \(L\) 分钟，而以为是任意的 \(L\) 分钟，感觉很不可做……
如果这样的话，这不就是憨憨状压了吗。
绷不住了。
最优子结构显然成立。
20221011
- [SDOI2012] 基站建设（\(\rm Easy\)）
计算几何是吧。
虽然这题计算几何的部分不多而且涉及关键，但还是很令人无语……
设发射点坐标 \(x_1\)，发射半径 \(r_1\)；接收点坐标 \(x_2\)，接受半径 \(r_2\)。
考虑 \((x_2-x_1)^2+(r_2-r_1)^2=(r_1+r_2)^2\)，
于是 \((x_2-x_1)^2=4r_1r_2\)，
从而 \(\sqrt{r_2}=\dfrac{x_2-x_1}{2\sqrt{r_1}}=\dfrac{x_2}{2\sqrt{r_1}}-\dfrac{x_1}{2\sqrt{r_1}}\)，
于是转移方程 \(f_i=\min\{\dfrac{x_i}{2\sqrt{r_j}}+(f_j-\dfrac{x_j}{2\sqrt{r_j}})|j<i\}+v_i\)。
妥妥的斜率优化，直接做就好了。
不幸由于没有满足区间包含单调性与四边形不等式，决策单调性并不满足。
然后转移还是半在线的，得 cdq 分治/二进制分组。
loj 上被卡常了。这么开小时限强迫人写平衡树/李超树不好吧。
卡常卡过去了。 - [SDOI2011] 拦截导弹（\(\rm Easy\)）
搁着强行考 cdq 分治是吧……
思维难度不大，写起来很丑。
而且这题命题也不严谨。完全可能会爆精。 - [SCOI2008] 奖励关（\(\rm Easy\)）
简单状压，逆推即可。 - [ZJOI2012] 波浪（\(\rm Hard\)）
这个拆贡献按 \(n\) 递增序枚举想的到，但没有想到这么设 dp 状态。
设完后就不难了。
申必数据分治还是差不多得了，为啥不考模意义。 - [HAOI2011] Problem c（\(\rm Easy\)）
容易想起 ZJOI 里一道叫做看电影的题目。
然而这里的做法不能照搬，因为那道题目的公式有特殊性质。
考虑几个显然的结论：
编号顺序对答案没有影响；可行的充要条件是 \(\forall k\in[1,n]\)，\(a_i\) 达到 \(k\) 的元素个数不超过 \(n-k+1\) 个。
于是，直接画出一张 Young 表，第 \(k\) 行有 \(n-k+1\) 个格子，要求每一行前若干个格子填 \(1\)，后若干个格子填 \(0\)，
使得第一行填满 \(1\)，每一行还要比后一行多出选 \(a_i\) 为 \(k\) 的人的个数个格子。
于是直接 dp，然后同时在 dp 时分配标号即可。
注意判断无解的情况。
诶复杂度是不是假的。
蛤，结果直接过了，瞄了眼题解，正解就是这个……
手动测了极限数据，跑得飞快，不开 O2 也只用 \(1{\rm s}\) 左右。 - CF1009F Dominant Indices（\(\rm Easy\)）
学了一下长剖优化 dp，重新写了一遍这题。