题目：P1987 摇钱树

$\text{蒟蒻在DP之路上求索着}$

这道题我一开始竟然觉得是区间DP

思路

看起来这道题我们可以以任何顺序来砍树,这就牵扯到先后砍树哪一种更优.如果我们要暴力的话,那就是枚举树的全排列,然后寻找最优解.可是如果我们不枚举,有没有办法通过一些方法判断出哪一棵树先砍呢?

还记得国王游戏吗,在那一题中我们讨论了邻项交换法来寻找贪心策略.我们不妨来尝试一下.

假设一棵树上的总钱数是$A$,每天掉落$a$个,另一棵树是$B$和$b$.我们先按照$A,B$的顺序在时间$x$和$x+1$砍掉.这时我们将会得到的收益为$A-ax+B-b(x+1)[1]$.而我们交换$AB$,得到的收益是$A-a(x+1)+B-bx[2]$,如果先砍$A$更优,那么我们要求$[1]$式-$[2]$式要大于0.经过整理,我们发现此时$a-b>0$,也就是$a>b$.现在我们可以得出结论了:先砍倒掉钱速度快的树更划算.因此我们要按照掉落速度从大到小排序.

但是我们只能砍掉K棵树,也就是说我们上文提到的$B$不一定能砍掉,然而我们的交换是在两棵树都能砍掉的前提下进行的,因此要有所取舍.这就是一个容量是K的01背包问题.设$f[j]$表示砍掉$i$棵树的最大值,那么我们不难得出:
$$
f[j]=max(f[j],f[j-1]+max(0,A[i]-a[i]\times (j-1)))(1\le i\le n,1\le j\le max(i,K))
$$
这样问题就解决了.因此贪心和DP有时也能有很好的结合.
当然了:

$\textit{多测不清空,爆零两行泪}$

——Gensokyo