社区讨论

在dp奇货的时候正序倒序循环（开o2后一个ac一个wa），为什么

ccjhspeed
P1782旅行商的背包参与者 4已保存回复 3

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
3 条
当前快照
1 份
快照标识符
@locc0swd
此快照首次捕获于
2023/10/30 11:20
2 年前
此快照最后确认于
2023/11/04 23:03
2 年前
查看原帖

（第4个循环组，第3层）

ac code

CPP
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+10;
int n,m,C;
int v[N],w[N],tt=0;
int a[N],b[N],c[N];
int V,W,D;
int dp[N];

 main(){
	cin>>n>>m>>C;
	for(int i=1;i<=n;i++){
		cin>>V>>W>>D;
		int x=1;
		while(D){
			if(x>D) x=D;
			v[++tt]=x*V,w[tt]=x*W,D-=x;
			x*=2;
		}
	} 
	for(int i=1;i<=m;i++) cin>>a[i]>>b[i]>>c[i];
	
	for(int i=1;i<=tt;i++){
		for(int j=C;j>=v[i];j--){
			dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
		}
	}
	
	for(int i=1;i<=m;i++){
		for(int j=C;j>=0;j--){
			for(int l=0;l<=j;l++)
				dp[j]=max(dp[j],dp[j-l]+a[i]*l*l+b[i]*l+c[i]);
		}
	}
	
	cout<<dp[C];
}

wa code

PASCAL
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+10;
int n,m,C;
int v[N],w[N],tt=0;
int a[N],b[N],c[N];
int V,W,D;
int dp[N];

 main(){
	cin>>n>>m>>C;
	for(int i=1;i<=n;i++){
		cin>>V>>W>>D;
		int x=1;
		while(D){
			if(x>D) x=D;
			v[++tt]=x*V,w[tt]=x*W,D-=x;
			x*=2;
		}
	} 
	for(int i=1;i<=m;i++) cin>>a[i]>>b[i]>>c[i];
	
	for(int i=1;i<=tt;i++){
		for(int j=C;j>=v[i];j--){
			dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
		}
	}
	
	for(int i=1;i<=m;i++){
		for(int j=C;j>=0;j--){
			for(int l=j;l>=0;l--)
				dp[j]=max(dp[j],dp[j-l]+a[i]*l*l+b[i]*l+c[i]);
		}
	}
	
	cout<<dp[C];
}

回复

共 3 条回复，欢迎继续交流。

正在加载回复...