求助
  • 板块学术版
  • 楼主Grace2022
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/7/18 11:08
  • 上次更新2024/7/18 11:56:49
查看原帖
求助
656125
Grace2022楼主2024/7/18 11:08

我在解决【https://www.luogu.com.cn/problem/P1782】问题,即【洛谷 P1782 旅行商的背包】时,WA了三个点。 求助大佬,请问我的代码哪儿错了?

#include<bits/stdc++.h>
using namespace std;
#define int long long
int v[2000500],w[1000500],a[10],b[10],c[10],dp[10005];
signed main(){
	int n,m,V,num=0;
	scanf("%lld%lld%lld",&n,&m,&V);
	for(int i=1;i<=n;i++){
		int x,y,s,t=1;
		scanf("%lld%lld%lld",&x,&y,&s);
		while(t<=s){
			v[++num]=t*x;
			w[num]=t*y;
			s-=t;
			t*=2;
		}
		if(s>0){
			v[++num]=s*x;
			w[num]=s*y;
		}
	}
	for(int i=1;i<=m;i++){
		scanf("%lld%lld%lld",&a[i],&b[i],&c[i]);
		for(int j=1;j<=V;j++){
			int x=j,y=a[i]*j*j+b[i]*j+c[i],s=m,t=1;
			while(t<=s){
				v[++num]=t*x;
				w[num]=t*y;
				s-=t;
				t*=2;
			}
			if(s>0){
				v[++num]=s*x;
				w[num]=s*y;
			}
		}
	}
	for(int i=1;i<=num;i++){
		for(int j=V;j>=v[i];j--){
			dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
		}
	}
	cout<<dp[V];
	return 0;
}
2024/7/18 11:08
加载中...