最大标志：选择恰好 \(K\) 个，使什么东西最优。
就比如说 \(f_{i,j}\) 表示前 \(i\) 个数里选 \(j\) 个的最优解。直接求解复杂度很寄。
如果 \(f_{n,x}\) 在坐标系里画出的是一个凸函数(\(x\) 是取了多少个值)，那么就可以进行 wqs 二分。
我们想要求当 \(x=K\) 时的解，因为是凸函数所以二分斜率，去用这个斜率切凸包，看对应的横坐标是什么。
具体的就是每个因为形如 \(y=kx+b\)，其中 \(kx\) 就是要在每次选的时候增加 \(k\) 的代价。
其实原理看看就行。然后还有细节。
- 二分的数据。因为正常情况下 \(f_{i,j}\) 都是整数，所以斜率是整数，所以就在整数内二分就行。如果 \(f_{i,j}\) 可能会有小数的情况，这时候就实数二分。
- 如果凸函数上有三点共线，那么直接二分是可能二分不到的。这时候需要自己分析选这条线段的哪一边）
题吧也没做几个好的。
P5896 [IOI2016]aliens
给一个 \(n\times n\) 的网格图，上面有一些关键点，需要以主对角线为对角线，画若干个正方形，求最小覆盖多少个方格使得所有点被覆盖。
emmmm，我不想写了。但是我有一个非常强的题解像挂在上面。
反正就是自己乱感性理解凸性，然后就斜率优化就行。
P5308 [COCI2018-2019#4] Akvizna
\(f_{i,j}\) 表示剩 \(i\) 个人，花了 \(k\) 轮的最大收益。
\(f_{i,j}=f_{k,j-1}+\frac {i-k}{i}\)
感性理解凸性，直接斜率优化www
P4983 忘情
双倍经验link
CF802O April Fools' Problem (hard)
被我扔到了模拟赛里。
就是首先考虑用 wqs 二分，感性理解凸性（肯定是增加量越大打印题目越少）
然后我们考虑如何找最优策略。
有两种情况，一种是 \(a\) 待匹配，另一种是贪心的选一个 \(a\) 匹配，用一个堆维护就行。