新开一个坑...
P2647 最大收益
考虑我们已经确定了取哪些数然后要确定顺序，发现如果答案排列是 (p_1,p_2...p_k)，那么答案为 (sum_{i=1}^n(w_{p_i}-(k-i)r_{p_{i}}))。
发现前面的和顺序无关，最后即要最小化 (sum_{i=1}^{n}(k-i)r_{p_{i}})，(k-i) 递减，那么 (r) 递增即为最小（排序不等式）。所以我们在一开始按 (r) 排序就和顺序无关，按从前往后的顺序取就好了。
然后就可以考虑 dp 了，记 (f[i][j]) 代表从前 (i) 个已经取了 (j) 个的最大值。
显然有状态转移方程：(f[i][j]=max(f[i-1][j]+f[i-1][j-1]+val(i)))，但是我们不知道后面还要取多少个数，显然可以再加一维，然后时间复杂度变为 (O(n^3)) 过不了。
重新设计状态，从后往前 dp，(f[i][j]) 代表从 (i) 到最后已经取了 (j) 个的最大值。
这里就可以这么转移了：(f[i][j]=max(f[i+1][j],f[i+1][j-1]+w_i-r_i imes (j-1)))。
P1966 火柴排队
将式子变形为 (sumlimits_{i=1}^{n}a_i^2+b_i^2-2a_ib_i)，发现即让 (sumlimits_{i=1}^{n}a_ib_i) 最大即可，根据排序不等式得 ({a},{b}) 都有序时最大，所以现在即要通过交换相邻两元素使得对于排序的元素对应。说白了就是 (a) 中最大的对应 (b) 中最大的， (a) 中次大的对应 (b) 中次大的，一次类推。给每个数一个编号，这样同值的数也区分开来。假设 (a) 的排名数组是 (ranka)，(b) 的排名数组是 (rankb)，构造 (work_{ranka_i}=rankb_i)，使这个数列有序的次数即为答案。这类交换相邻两个元素的题都可用逆序对来做。
P3620 数据备份
这是近乎一道反悔贪心的模板。反悔贪心其实就是在模拟费用流的回流（退流）的过程，往往就是选当前这一步可能并不是最优，进而再加入一个不选当前这个的答案。
现在回到这道题，考虑记 (d_i) 为第 (i) 个和第 (i-1) 个之间的距离，那么假设我们选定一个最小的 (d_i)，答案加上 (d_i) 那么 (i-1) 和 (i+1) 就都不能选了。可是有可能选 (i-1) 和 (i+1) 更优，所以我们加入一个 (d_{i-1}+d_{i+1}-d_i) 的在 (i) 的位置上，代表选 (i-1) 和 (i+1) 但不选 (i)。容易证明这样选 (k) 次即为答案。由于需要找最小值所以需要一个堆，由于和i-1、i+1有关所以需要一个链表。
P3833 魔法树
这是一道树链剖分的模板，就不讲了。
下面的题没时间写题解了，先咕一下吧qwq