P2340 背包——RE之光
  • 板块学术版
  • 楼主Inter12
  • 当前回复2
  • 已保存回复2
  • 发布时间2023/10/6 13:26
  • 上次更新2023/11/2 15:16:54
查看原帖
P2340 背包——RE之光
995952
Inter12楼主2023/10/6 13:26

有谁能看一下这题,RE好严重

#include<bits/stdc++.h>
//有问题 
#define int long long
using namespace std;
const int N=8e5+5,delta=4e5+5;
int n,iq[405],eq[405],ziq,dp[N];
signed main() {
	cin>>n;
	memset(dp,0xcf,sizeof(dp));
	dp[delta]=0;
	for(int i=1;i<=n;i++) {
		cin>>iq[i]>>eq[i];
		if(iq[i]>=0)
			ziq+=iq[i];
	}
	for(int i=1;i<=n;i++) {
		if(iq[i]>=0)
			for(int j=ziq+delta;j>=iq[i];j--)
				dp[j]=max(dp[j],dp[j-iq[i]]+eq[i]);
		else
			for(int j=iq[i];j<=ziq+delta+iq[i];j++)
				dp[j]=max(dp[j],dp[j-iq[i]]+eq[i]);
	}
	int ans=0;
	for(int i=delta;i<=delta+ziq;i++)
		if(dp[i]>=0)
			ans=max(ans,dp[i]+i-delta);
	cout<<ans;
	return 0;
}

[https://www.luogu.com.cn/record/127864215]

2023/10/6 13:26
加载中...