[GESP202512 六级] 道具商店

题干分析

题目描述已足够清楚，这里不多做赘述。

---

思路

看完题目可以发现，只是一道 0-1 背包板子题，直接交：

#include<bits/stdc++.h>
using namespace std;
int n,k,a[505],c[505];
int main(){
    cin>>n>>k;
    int f[k+1];
    memset(f,0,sizeof(f));
    for(int i=1;i<=n;i++){
        cin>>a[i]>>c[i];
    }
    f[0]=0;
    for(int i=1;i<=n;i++){
        for(int j=k;j>=c[i];j--){
            f[j]=max(f[j],f[j-c[i]]+a[i]);
        }
    }
    cout<<f[k];
}

可是，$MLE$ 了！
一看数据范围：
$1 \le k \le 10^9$
所以，我们要对 0-1 背包的做法进行一些改动。
我们将 $f_j$ 设为攻击力为 $j$ 所要花费的最少金币，那么状态转移方程为：

$$f_j \gets \min(f_j,f_{j-a_i}+c_i)$$

然后输出要从 $250000$ 开始，到 $0$ 结束，如果有 $f_i \le k$，那么输出 $i$。

---

代码

没有代码，自己想去吧。