题解 P4823 【[TJOI2013]拯救小矮人】

2019-04-25 10:25:15


题解里似乎都是一维 $\mathrm{DP}$ ,窝发一个辣鸡的二维 $\mathrm{DP}$ 的做法qwq


贪心 + $\mathrm{DP}$ 。

首先把所有小矮人按 $a+b$ 从小到大排序,这样子可以保证如果 $x$ 比 $y$ 先走,那么 $x$ 在序列中在 $y$ 的前面。

然后考虑 $\mathrm{DP}$ 。设 $f[i][j]$ 表示前 $i$ 个人走了 $j$ 个的最大高度。显然边界为 $f[0][0]=0$ 。

转移的话,考虑 $i$ 走不走。

  • 如果不走的话,用 $f[i-1][j]$ 来更新 $f[i][j]$ 。
  • 如果走的话,用 $f[i-1][j]$ 来更新 $f[i][j+1]$ 。

注意走是有条件的: $f[i-1][j]+s[i+1]+a[i]+b[i]\geq H$ 。这里的 $s$ 表示 $a$ 的后缀和。

这个条件应该比较容易理解,就是后面的全部堆起来,加上前面的人,再加上自己的高度能否出去。

答案就是最大的使得 $f[n][i]$ 被更新过的 $i$ 。

具体实现及细节见代码