ABC410E题解

可能更洛谷的体验

有一个$O(n^3)$ 的 DP 是很显然的，就是设$f(i,j,k,0/1)$ 表示第$i$ 只怪兽，用了$j$ 的体力，用了$k$ 的魔力，当前打怪兽用不用魔力的最大打怪兽数量，这显然不能通过。

我们考虑什么状态中信息是有用的。首先，既然我们是一个一个按顺序打的怪物，遇到每一个怪兽我们肯定都要打。那么实际上我们根本就不用存储打怪兽的数量，只需要存储当前魔力或体力的信息，通过这个我们来判断是否到现在能够打怪兽。

那么，我们只需要把体力或魔力任一维度丢到我们 DP 求解的答案即可，因为这里我们有一个是否使用魔力的状态决策，我们考虑把魔力丢进去。

设$f(i,j,0/1)$ 表示第$i$ 只怪兽，用了$j$ 的体力，当前打怪兽用不用魔力的最小魔力使用。转移方程是显然的：

$$\begin{aligned} f(i,j,0) & = \min \left\{ f(i-1,j+a_{i},0),f(i-1,j+a_{i},1) \right\} \\ f(i,j,1) & = \min \left\{ f(i-1,j,0),f(i-1,j,1) \right\} +b_{i} \end{aligned}$$

答案统计即求最大的$i$ 使得$\min\limits_{j=1}^{h} \left\{ f(i,j,0),f(i,j,1) \right\}\le M$。

代码如下：

#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int MN=3520;
int f[MN][MN][2],n,h,m,a[MN],b[MN];

signed main(){
    cin>>n>>h>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i]>>b[i];
    }
    memset(f,0x3f,sizeof(f));
    for(int i=0;i<=h;i++){
        f[0][i][0]=f[0][i][1]=0;
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j+a[i]<=h;j++){
            f[i][j][0]=min(f[i-1][j+a[i]][0],f[i-1][j+a[i]][1]);
        }
        for(int j=0;j<=h;j++) 
            f[i][j][1]=min(f[i-1][j][0],f[i-1][j][1])+b[i];
    }
    bool flag=0;
    for(int i=n;i>=1;i--){
        int ans=0x3f3f3f3f3f3f3f3f;
        for(int j=0;j<=h;j++){
            ans=min({ans,f[i][j][0],f[i][j][1]});
        }
        if(ans<=m){
            flag=1;
            cout<<i;
            break;
        }
    }
    if(!flag) cout<<0;
    return 0;
}