DP？
QwQ这题似乎不能直接贪心2333——
阶段
很明显的阶段性，(n)关便为(n)个阶段，
状态
分好阶段后，容易构造出状态的表达：
(f[i,j])表示Ma5termind在最开始要带(f[i,j])个子弹，才能打到第(i)关，并打倒第(i)关第(j)个敌人。
状态转移
Ma5termind在第(i)关获得的敌人的子弹只能使用到第(i+1)关。
可见当前状态是由上一个阶段(即(i-1))推过来的
于是我们得到这么个状态转移方程：
假的End
70分愉快的炸啦2333
优化？贪心？
没错，就是贪心啦
官方题解中用map和vector实现了一个很玄学的贪心，让我们来分析一下把！
因为(p[i,j])是一个常数，于是我们可以把dp方程变为：
所以每个状态更新时就变成了最值查找啦，强行qsort就发挥作用啦！
然后我们就可以用接近(O(m))的时间复杂度寻找更新状态啦。
我们使用map1存上一阶段的状态map，map2为当前阶段的map，
先考虑第二种情况
一言不合上代码：
j:=1; k:=1; tmp:=maxlongint;
while j<=m do
begin
while (k<=m) and (map1_b[k]<=map2_p[j]) do
begin
tmp:=min(tmp,map1_f[k]-map1_b[k]);
inc(k);
end;
f[i,map2_j_num[j]]:=min(f[i,map2_j_num[j]],tmp+map2_p[j]);//别忘记加上常数p
inc(j);
end;
这个操作的时间复杂度忽略常数接近(O(m)),为什么是对的？
班门弄斧地证明一下2333,我们用类似数学归纳法的方法证明——
对于j
我们先称满足(map1_b[k] leq map2_p[j])在map1的([1,k])区间为对于当前状态(f[i,j])的最小满足区间
在这个区间里，那么因为是按照(map1_b)为关键字升序排序的，所以后面的(map1_b[k])都会大于(map2_p[j])
所以显然,当前检查到([1,k])是对于当前状态(f[i,j])的最小满足区间，那么这区间中最小的(f[i-1,k]-b[i-1,k])(即(tmp))对于(j)是最优的 (满足条件(b[i-1,k]<=p[i,j])情况下)
对于j+1？
又因为这个map2_p是按照升序,所以(j+1)的(p)是大于当前(j)的，
那么如果(j+1)时不更新(k)，也就是说(tmp)不会变，这意味着([1,k])也是他的最小满足区间,所以这个区间中最小值(tmp)也是对于(j+1)最优的 (满足条件(p[i,j]>b[i-1,k])情况下)
如果更新的话，那就和对于j的情况是类似的啦,我们会继续找到最小满足区间然后更新。
类似的，对于第一种情况，我们也能按照类似这样的方法证明和更新状态，时间复杂度约为(O(n imes m imes log_2^m))，空间复杂度约为(O(n imes m))