Card scoring
题面：
共 \(n\) 张牌，给定一个 \(k~(2\le k\le 4)\) 每张牌有个种类 \(a_i(1\le a_i\le n)\) 按从小到大的顺序取牌，每张牌可以选 或 不选，每个时刻只允许手中只有一个种类的牌。每个时刻可以结算手中的牌的分值，假如手中有 \(x\) 张牌, 获得的分是 \(x^{\frac{k}{2}}\) 问最多能获得多少分。
题解:
设 \(f_i\) 表示前 \(i\) 表示选到第 \(i\) 张牌，且第 \(i\) 张牌被选的答案。\(f_i(a_i=a_j)=max(f_{j-1}+(s_i-s_j+1)^{\frac{k}{2}})\)，与 \(i\) 和 \(j\) 相关，考虑决策单调性，但无法直接斜率优化因为涉及开根。因为 \((s_i-s_j+1)^{\frac{k}{2}}\) 的导函数恒正，即单调递增，当 \(f_j\) 比 \(f_k\) 转移优 \((j<k)\)，维护单调栈，对于栈顶的两个元素，二分前一个替换掉后一个的最早时间，到时间时就把它弹出栈顶。
Minimum cost road:
题面：
每个边有个维护的代价，和一个长度，要求去掉一些边，使得每两点之间的最短路不变，让总的维护代价最小，求这个代价。（边数，点数都小于 \(2\times 10^3\)）
题解：
按代价从大到小排序，枚举每个边去掉后边所连的2点间最短距离不变，可删。