题解：AT_abc410_e [ABC410E] Battles in a Row

[原题](https://atcoder.jp/contests/abc410/tasks/abc410_e)

读完题目之后还以为是贪心，但是这么简单放到 e 题又不是太合适，所以重新思考一下：击败怪物有两种方式（消耗体力或者魔力），并且要让击败的怪物数量最大化，那不就是 dp 吗？

定义数组 $dp$，那么 $dp[i]$ 表示剩余体力为 $i$ 时消耗的最小魔力，由于我们的 $dp$ 数组不是保存的答案，所以我使用了一个临时数组 $dp_f$ 来防止覆盖 $dp$ 数组。

在遍历的过程中：定义一个检查标志 $check$ 表示当前怪物是否可击败并初始化为 false，将临时数组 $dp_f$ 初始化为 $inf$，用于存储处理当前怪物后的新状态；随后从 $j=0 \rarr h$ 遍历一下剩余的体力值，我们令 $nowa,nowb$ 分别表示打败当前怪物所需要的 $a,b$：

- 不使用魔法：若当前剩余体力 $j \ge nowa$ 且上一状态 $dp[j-nowa]$ 可达，则更新 $dp_f[j]$ 为 $dp[j - nowa]$（魔力不变）；

- 使用魔法：若上一状态 $dp[j]$ 可达，则更新 $dp_f[j]$ 为 $dp[j]+nowb$（魔力增加）；

- 若 $dp_f[j] \le w$，则标记 $check=true$（当前怪物可击败）；

- 检查当前标志 $check$ 是否为 false，如果是，那么证明当前能打败的怪物数量已经顶天了，所以直接输出 $i$ 跑路即可；

- 最后将 $dp_f \rarr dp$ 继续处理下一个怪物。

别忘了，如果所有怪物都能被打败，在循环结束后输出 $n$ 即可。

那么为什么要检查 $dp_f[j] \le w$ 呢？因为每处理一个怪物后，检查是否存在剩余体力 $j$  使得消耗魔力不超过初始魔力 $w$，若不存在，则无法击败当前怪物，那么输出当前击败的怪物数量即可。

代码里有注释，希望大家给予批评纠正。

## Code:
```cpp
#include<bits/stdc++.h>
#define int long long
#define Sangonomiya signed
#define Kokomi main()
#define Love return
#define Nahida 0
#define Forever ;
#define IOS cin.tie(nullptr)->sync_with_stdio(false)
#define cin std::cin
#define cout std::cout
const int N=1e6+5;
const int inf=0x3f3f3f3f;
int n,h,w;
int a[N],b[N];
int dp[N],dp_f[N];//dp数组：dp[j]表示剩的最小魔力；dp_f用于临时存储更新后的状态
bool check=false;//标记当前怪物是否能被击败
Sangonomiya Kokomi{
    IOS;
    cin>>n>>h>>w;
    for(int i=0;i<n;i++) cin>>a[i]>>b[i];
    //初始化dp数组：剩余体力为j时消耗的最小魔力，初始化为无穷大（不可达状态）
    for(int i=0;i<=h;i++) dp[i]=inf;
    dp[0]=0;//初始状态：剩余体力为0时消耗魔力为0
    //接下来遍历每个怪物
    for(int i=0;i<n;i++){
        int nowa=a[i];
        int nowb=b[i];//当前怪物的体力消耗和魔力消耗
        //初始化临时dp_f数组为无穷大
        for(int j=0;j<=h;j++) dp_f[j]=inf;
        check=false;//重置检查标志
        //遍历所有可能的剩余体力值j（0到h）
        for(int j=0;j<=h;j++){
            //选择1：不使用魔法（仅当剩余体力j>=当前怪物体力消耗nowa，且上一状态dp[j-nowa]可达时）
            if(j>=nowa&&dp[j-nowa]!=inf){
                //更新状态：剩余体力j由上一状态j-nowa转移而来，魔力消耗不变
                if(dp_f[j]>dp[j-nowa]){
                    dp_f[j]=dp[j-nowa];
                }
            }
            //选择2：使用魔法（仅当上一状态dp[j]可达时）
            if(dp[j]!=inf){
                //更新状态：剩余体力j不变，魔力消耗增加nowb
                if(dp_f[j]>dp[j]+nowb){
                    dp_f[j]=dp[j]+nowb;
                }
            }
            //检查当前状态是否可达（消耗魔力不超过初始魔力w）
            if(dp_f[j]<=w){
                check=true;//标记当前怪物可击败
            }
        }
        //如果当前怪物无法被击败，输出已击败的怪物数量（i）并结束
        if(!check){
            cout<<i;
            return 0;
        }
        //更新dp数组为处理完当前怪物后的状态
        for(int j=0;j<=h;j++) {
            dp[j]=dp_f[j];
        }
    }
    // 所有怪物都被击败，输出n
    cout<<n;
    Love Nahida Forever;
}
```

正在渲染内容...