MonstersValley

作者:陆宇暄

关键词:动态规划

题目简述

给定一个长度为$n$的序列,序列上的每个位置有一个怪物,每个怪物有一个智商值$d[i]$和一个攻击力$p[i]$,现在你要从序列的最左端走到序列的最右端,你的智商值初始是$0$,当你遇到一个智商严格比你高的怪物的时候必须打死它并获得它的智商,否则可以不打这个怪也可以打死它并获得它的智商,问你最后最少受多少伤害.

保证$d[i] \leq 1e12$,$p[i]$是$1$或$2$,$n \leq 50$.

算法一

由于$n \leq 50$,所以可以考虑双向搜索,对于前$n/2$个位置枚举所有打或不打怪的情况,后$n/2$个位置也枚举所有打或不打怪的情况并顺便计算如果该情况合法则需要的最小智商.

做完这部之后可以用一次快速排序或归并得到后$n/2$个位置每个智商区间所受到的最小伤害.

同样可以用快速排序或归并的方法把前$n/2$个位置的情况做到有序,然后统计答案即可.

时间复杂度: 归并:$O(2^{n/2})$ 快速排序:$O(2^{n/2}\times n)$ 空间复杂度: $O(2^{n/2})$

算法二

嗯,算法一特别蠢......

令$f[i][j]$表示走到第$i$个位置受到至多$j$点伤害时的最高智商,转移如下:

f[i][j]=f[i][j-1];  
if (j-p[i]>=0) f[i][j]=max(f[i][j],f[i-1][j-p[i]]+d[i]);  
if (f[i-1][j]>=d[i]) f[i][j]=max(f[i][j],f[i-1][j]);  

最终答案就是最小的一个$j$使得$f[n][j]$不是无解.

时间复杂度: $O(n^2)$ 空间复杂度: $O(n^2)$ 可以使用滚动数组达到 $O(n)$