不可视境界线

转移 : $f[i][j]=\max\limits_{k=1}^{i-1}f[k][j-1]+c(k,i)$

需要预处理反三角函数，用WQS二分,把原问题转化为:

每选一个附加一个贡献$mid$,不考虑个数限制的$log$个DP子问题。

转移 : $f[i]=\max\limits_{k=1}^{i-1}f[k]+c(k,i)+mid$

没有决策单调性根本玩不动，二分栈再优化。

字符串重排

建出给定串的字典树，并在每个串的末尾节点挂一个叶子表示这个串。

那么所有最优序列一定是字典树的所有 dfs 序的叶子部分。考虑 u 必须恰好接在 v 后的限制，就相当于限制了 u 到 lca 路径上的每个点最后 dfs 到的儿子，以及 v 到 lca 路径上的每个点最先 dfs 到的儿子，以及 lca 的某两个儿子在 dfs 时先后顺序。

Mole Tunnels

可以作为理解模拟费用流思想的题。

不可视境界线【环版本】

可以作为$dp$优化和分析难度上的压轴了。

How Many of Them

计数$DP$

心跳

构造题。

禁断之门对面，是此世还是彼世

观察规律加上优化。

深搜

观察规律，全局平衡树维护动态$DP$。

最大权独立集问题

大力讨论。

序列变换

观察得结论题。

雪的魔法

观察得结论题。

蓬莱药局

细节题，数据点分治，

How to AK NOI?

算法题，考验观察敏锐度。

Mobile Service

考验状态和状态机的设计能力。

ボディーガード

考验$DP$和$DP$优化的题目。

巧克力

随机化。

排列

神仙科技题。