闲扯
学到了, $dp$ 原来还有这种骚操作,是我以前太菜了。。
题面
Solution
我们设 $dp_{i,j}$ 表示考虑前 $i$ 个人,分出去了 $j$ 个饼干时的最小怨气总和。
首先,我们明确一个事实:贪婪度大的孩子应该拿到更多的糖果。这很容易通过邻项交换证明。
但是怨气值和比每个孩子得到的糖果多的人数有关,这个不好记录。
我们这样考虑:
- 若当前考虑到了第 $i$ 个人(从大到小考虑),且他的糖果数大于 $1$ ,那么我们将每个人的糖果数减去 $1$ ,相对大小不会改变,答案也不变,即 $dp_{i,j}=\min(dp_{i,j},dp_{i,j-i})$ 。
- 若第 $i$ 个人的糖果数等于 $1$ ,我们枚举有几个人比他多,即 $dp_{i,j}=\min_{k=0}^{i-1}(dp_{i,j},dp_{k,j-(i-k)}+k\cdot \sum_{p=k+1}^i g_p)$ 。
时间复杂度: $O(n^2m)$ 。
Code
1 |
|