T1
一眼背包，但是很怪
考虑设dp[i][j][k]表示前i个物品还剩j个月饼还剩k个冰激凌。 $O(n^4)$ 显然。
转移O(n)枚举用钱还是优惠券。
瓶颈在于冰激凌的优惠。考虑如何把这一维优惠掉。
不难想到贪心，如果把优惠排序，那么如果你有优惠券你要买牛的话你一定会先花优惠券买，这样就好做了，因为这样转移变成了 $O(1)$ 并且发现 $dp[i][j!=x][k] $ 的第三维是没有任何用处的，即你上一个购买的花了月饼，这次购买用优惠券一定不如上个用优惠券，这次购买没有优惠券了用月饼优的。
复杂度变成 $O(n^2)$。
T2
考虑固定一个起始山 $i$，枚举一个 $j(i<j)$ 。表示i与j连一个线段，考虑维护一个之前最大斜率，如果当前线段的斜率比他之前的大，那么显然他有用，ans++，每个点用一个set维护起作用的有哪些点。
考虑带修改，假如把x拔高k，那么比x小的点都可能会被影响，被影响的区间就是当前这个点拔高后的斜率到第一个斜率比它大的点都要被删除。set维护一下，复杂度玄学 $O(n^2logn)$，5000ms开O3才能过4900ms过
T3
人类智慧
题意：选出几个点，去掉连向外面的边，权值为选出的点数 $\times$ 和每个点的度数最小值。
考虑一个最优的情况，就是完全图，这时候它的第二个系数最大值才是 $\sqrt m$，所以我们考虑深入去想第二个系数。
选点，不去想，考虑所有点都存在，每次把不优秀的点删掉。
考虑第二个系数为i时，那每个度数 $<i$ 的点就需要被删除，那我们想到什么，拓扑排序啊！
我们枚举第二个系数从 $1-\sqrt m$，我们每次都把度数为 $i-1$ 的点全删掉然后dfs求一下连通块最大个数，对ans取max，做完了。
代码很短
复杂度 $O((n+m) \sqrt m)$。
标签：优惠券,题解,复杂度,USACO,枚举,系数,Au,sqrt,考虑 From： https://www.cnblogs.com/ysQwQ/p/17030531.html