在dp奇货的时候正序倒序循环(开o2后一个ac一个wa),为什么
查看原帖
在dp奇货的时候正序倒序循环(开o2后一个ac一个wa),为什么
238784
cjhspeed楼主2021/5/19 20:17

(第4个循环组,第3层)

ac code

#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

#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];
}
2021/5/19 20:17
加载中...