01背包0分求助

a2lyaXNhbWUgbWFyaXNh @ 2022-08-24 14:12:39

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
int w[2050],c[2050],dp[114514];
int ans=2e12;
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>w[i]>>c[i];
        w[i]++;
        m=max(m,w[i]);
    }
    m+=n;
    for(int i=1;i<=n;i++)
        for(int j=m;j>=w[i];j--)
            dp[j]=min(dp[j],dp[j-w[i]]+c[i]);
    for(int i=1;i<=m;i++)
        ans=min(ans,dp[i]);
    cout<<ans;
    return 0;
}

by Demeanor_Roy @ 2022-08-24 14:17:41

开 long long

by Demeanor_Roy @ 2022-08-24 14:18:30

@S__B 对 dp 数组初始化

by a2lyaXNhbWUgbWFyaXNh @ 2022-08-24 14:21:32

@Demeanor_Roy 额，说了初始化没用，而且用#define开了long long了

by xrxtcl @ 2022-08-24 14:29:53

最后一个for循环改成：

for(int i=n;i<=m;i++)

by xrxtcl @ 2022-08-24 14:30:15

@S__B

by a2lyaXNhbWUgbWFyaXNh @ 2022-08-24 14:30:51

@xiao_rui_xuan 好的，我试试

by xrxtcl @ 2022-08-24 14:31:47

@S__B 对着题解一个字母一个字母帮你看的

by a2lyaXNhbWUgbWFyaXNh @ 2022-08-24 14:32:38

好的。不用试都知道是错的。

by xrxtcl @ 2022-08-24 14:33:43

@S__B az

by AKNOI的梓钦 @ 2022-08-24 14:43:50

对 \text{dp} 数组初始化，并且将最后一个循环改为 for(int i=n;i<=m;i++)，亲测 AC。

现在你谷人做题都不看题不初始化的吗