题目
题意：有n只怪兽，每只怪兽在
k
i
k_i
ki时间点会出现，且生命值为
h
i
h_i
hi。现在我们需要消灭这
n
n
n只怪兽。由于我们每次打气功，都需要从1开始累计，比如上一秒是打的气功是x，那么这一秒可以打x+1，或者选择重新开始，气功为1。如果上一秒没有打气功，则这一秒只能打1。要消灭这
n
n
n只小怪兽，我们总共需要消耗的最小气功是多少。
思路：
先根据每只小怪兽的生命值，计算消灭这只小怪兽，需要从哪里开始打气功
p
o
s
i
pos_i
posi，比如
k
i
=
6
,
h
i
=
3
k_i=6,h_i=3
ki=6,hi=3，说明我们需要在时间点6-3+1=4的位置开始打气功。如果要批量处理连续区间内的小怪兽，我们需要计算区间
[
l
,
r
]
[l,r]
[l,r]的最小打气功的开始位置
p
p
p，然后计算从
p
p
p到
k
r
k_r
kr的气功总和即可。
由于本题的n比较小，可以支持 n 2 n^2 n2的复杂度。我们可以用dp。令 d p i dp_i dpi表示从i位置结束需要的最小气功。那么 d p i = d p j − 1 + d e a l ( j , i ) , ( 0 < j < = i ) dp_i = dp_{j-1} + deal(j,i),(0
