DP？
QwQ这题似乎不能直接贪心2333——
阶段
很明显的阶段性，\(n\)关便为\(n\)个阶段，
状态
分好阶段后，容易构造出状态的表达：
\(f[i,j]\)表示Ma5termind在最开始要带\(f[i,j]\)个子弹，才能打到第\(i\)关，并打倒第\(i\)关第\(j\)个敌人。 状态转移
Ma5termind在第\(i\)关获得的敌人的子弹只能使用到第\(i+1\)关。
可见当前状态是由上一个阶段(即\(i-1\))推过来的
于是我们得到这么个状态转移方程：
\[ \begin{cases} f[i,j]=min(f[i-1,k]|1 \leq k \leq n)&\text{当}b[i-1,k]>p[i,j]\\ f[i,j]=min(f[i-1,k]+p[i,j]-b[i-1,k]|1 \leq k \leq n) &\text{当}b[i-1,k] \leq p[i,j] \end{cases} \]
假的End
70分愉快的炸啦2333
优化？贪心？
没错，就是贪心啦
官方题解中用map和vector实现了一个很玄学的贪心，让我们来分析一下把！ 因为\(p[i,j]\)是一个常数，于是我们可以把dp方程变为：
\[ \begin{cases} f[i,j]=min(f[i-1,k]|1 \leq k \leq n)&\text{当}b[i-1,k]>p[i,j]\\ f[i,j]=min(f[i-1,k]-b[i-1,k]|1 \leq k \leq n)+p[i,j] &\text{当}b[i-1,k] \leq p[i,j] \end{cases} \]
所以每个状态更新时就变成了最值查找啦，强行qsort就发挥作用啦！
然后我们就可以用接近\(O(m)\)的时间复杂度寻找更新状态啦。
我们使用map1存上一阶段的状态map，map2为当前阶段的map，
先考虑第二种情况
\[f[i,j]=min(f[i-1,k]-b[i-1,k]|1 \leq k \leq n)+p[i,j] \text{当}b[i-1,k] \leq p[i,j]\] 一言不合上代码：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\times m\times log_2^m)\)，空间复杂度约为\(O(n \times m)\)