为什么不对啊

原题链接：105547.[GESP202512 六级] 道具商店

互关🐱‍🚀

2026-03-13 18:19:54

发布于：广东

34阅读

0回复

0点赞

#include<bits/stdc++.h>
using namespace std;
const int N=250010;
long long n,m,dp[N],w[N],v[N];
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>w[i]>>v[i];
    }
    for(int i=1;i<=N;i++){
        dp[i]=1e18;
    }
    dp[0]=0;
    for(int i=1;i<=n;i++){
        for(int j=N;j>=v[i];j--){
            dp[j]=min(dp[j],dp[j-v[i]]+w[i]);
        }
    }
    int sum=0;
    for(int i=1;i<=N;i++){
        if(dp[i]<=m){
            sum=i;
        }
    }
    cout<<sum;
}

有帮助，赞一个

去预览

0/2000

全部评论 4

很烫的凉水
首先，N是数组边界，你从N开始遍历会导致未定义行为（UB）引发未知错误。
其次，我没看出来您将战斗力当作体积来处理，在您的转移里，一直都是使用标准 01 背包模板做的，这不可能正确。

10小时前来自广东
0
Wang Yang
sa

15小时前来自浙江
0
很烫的凉水
代码帮你改完了，自己查收

昨天来自广东
0

很烫的凉水

首先，N是数组边界，你从N开始遍历会导致为定义行为（UB）引发为止错误。
其次，我没看出来您将战斗力当作体积来处理，在您的转移里，一直都是使用标准 01 背包模板做的，这不可能准确。

#include<bits/stdc++.h>
using namespace std;
const int N=250010;
long long n,m,dp[N],w[N],v[N];
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>w[i]>>v[i];
    }
    for(int i=1;i<=N-1;i++){
        dp[i]=1e18;
    }
    dp[0]=0;
    for(int i=1;i<=n;i++){
        for(int j=N-1;j>=w[i];j--){
            dp[j]=min(dp[j],dp[j-w[i]]+v[i]);
        }
    }
    int sum=0;
    for(int i=1;i<=N-1;i++){
        if(dp[i]<=m){
            sum=i;
        }
    }
    cout<<sum;
}

昨天来自广东

全部评论 4

热门讨论