关键信息：k 高达 1e9，但 aᵢ ≤ 500，n ≤ 500，所以总攻击力 s = Σaᵢ ≤ 250000。

这题不能按「金币 k」做容量（太大），要反过来：把攻击力当作容量，求达到每个攻击力所需的最小金币数。

你的代码问题

你的 dp 定义其实是 对的方向（dp[j] = 达到攻击力 j 的最小金币），但有一个逻辑错误：

for(int j=s;j>=a[i];j--)
    dp[j]=min(dp[j],c[i]+dp[j-a[i]]);

这是 01 背包的倒序写法 —— 而本题「每件道具只能购买一次」，正是 01 背包，所以倒序 ✅ 没错。

所以你的代码逻辑基本正确！问题在细节：

⚠️ 问题 1：INF 溢出

dp[i] = 2e9 + 100;   // 2147483747

dp[j-a[i]] 若是 INF，加 c[i]（可达 1e9）→ 溢出 int，得到负数，导致错误答案。

改成 0x3f3f3f3f（约 1.06e9）或直接用 1e18 配 long long：

const int INF = 0x3f3f3f3f;

⚠️ 问题 2：c[i] 是 1e9 级别，dp 值可能超 int？

dp[j] 最大是「买一堆道具的总金币」，理论上可达 n×1e9 = 5e11，会溢出 int！

但由于我们只关心 dp[j] <= k (1e9)，一旦超过就可以当「不可达」。用 long long 更安全：

long long dp[250005];

⚠️ 问题 3：找答案的循环

for(int i=0;i<=s;i++)
    if(dp[i]<=k) maxn=i;

正序 + 不 break，效率低。倒序找到就停：

for(int i=s;i>=0;i--)
    if(dp[i]<=k){ cout<<i; break; }

✅ 修正版

#include<bits/stdc++.h>
using namespace std;
const long long INF = 1e18;
int n, k, s;
int a[505], c[505];
long long dp[250005];
int main(){
    cin >> n >> k;
    for(int i=1;i<=n;i++){
        cin >> a[i] >> c[i];
        s += a[i];
    }
    fill(dp, dp+s+1, INF);
    dp[0] = 0;
    for(int i=1;i<=n;i++)
        for(int j=s;j>=a[i];j--)
            dp[j] = min(dp[j], c[i] + dp[j-a[i]]);
    for(int i=s;i>=0;i--)
        if(dp[i] <= k){ cout << i; break; }
    return 0;
}

复杂度

· 时间：O(n·s) = 500 × 250000 = 1.25e8，能过（GESP 一般 1s 内，稍紧但可接受） · 空间：250005 × 8 ≈ 2MB，OK

一句话总结

你的思路正确，倒序也对（每件只能买一次 = 01 背包）。核心 bug 是 INF 用 2e9+100 会溢出，改 0x3f3f3f3f 或换 long long 即可。

受着