[noip2006]金明的预算方案

发表于 2016-11-09   |   分类于 背包问题 , 动态规划  |  访问: 46 次

水了一个下午,各种水,结果机房其他人都写出来了,我都还徘徊在90分。。。

90分用的是dfs

处理出背包的物品,再用01背包跑一遍

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int _maxn=33000;
int dp[_maxn],n,m,a[80],b[80],c[80],fu[80][5],w[80],u[80],e,ans;
void dfs(int x,int y){
	int v;
	if(x==m+1){
		memset(dp,0,sizeof(dp));
		for(int i=1;i<y;i++)
			for(int j=n;j>=w[i];j--)
				if(dp[j]<dp[j-w[i]]+u[i])
					dp[j]=dp[j-w[i]]+u[i];
		ans=max(ans,dp[n]);
		return;
	}
	if(c[x])
		dfs(x+1,y);
	else{
		w[y]=a[x];
		u[y]=a[x]*b[x];
		dfs(x+1,y+1);
		if(fu[x][0]){
			v=fu[x][1];
			w[y]=a[x]+a[v];
			u[y]=a[x]*b[x]+a[v]*b[v];
			dfs(x+1,y+1);
		}
		if(fu[x][0]==2){
			v=fu[x][2];
			w[y]=a[x]+a[v];
			u[y]=a[x]*b[x]+a[v]*b[v];
			dfs(x+1,y+1);
			int v1=fu[x][1];
			w[y]=a[x]+a[v1]+a[v];
			u[y]=a[x]*b[x]+a[v]*b[v]+a[v1]*b[v1];
			dfs(x+1,y+1);
		}
	}
}
int main(){
	scanf("%d%d",&n,&m);
	int v;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&a[i],&b[i],&c[i]);
		if(c[i])
			fu[c[i]][++fu[c[i]][0]]=i;
	}
	dfs(1,1);
	printf("%d\n",ans);
	return 0;
}

一百分代码实现蛋疼点,因为要写四五种情况判断,再跑01背包

#include <cstdio>
#include <iostream>
using namespace std;
const int _maxn=33000;
int dp[_maxn],n,m,a[80],b[80],c[80],f[80][5];
bool have[_maxn][70];
int main(){
	scanf("%d%d",&n,&m);
	int e=0,x,y,z;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&a[i],&b[i],&c[i]);
		b[i]*=a[i];
		if(c[i])
			f[c[i]][++f[c[i]][0]]=i;
	}
	for(int i=1;i<=m;i++){
		if(!c[i]){
			for(int j=n;j>=a[i];j--){
				if(dp[j]<dp[j-a[i]]+b[i])
					dp[j]=dp[j-a[i]]+b[i];
				if(f[i][1]){
					if(j>=a[i]+a[f[i][1]])
						if(dp[j]<dp[j-a[i]-a[f[i][1]]]+b[i]+b[f[i][1]])
							dp[j]=dp[j-a[i]-a[f[i][1]]]+b[i]+b[f[i][1]];
				}
				if(f[i][2]){
					if(j>=a[i]+a[f[i][2]])
						if(dp[j]<dp[j-a[i]-a[f[i][2]]]+b[i]+b[f[i][2]])
							dp[j]=dp[j-a[i]-a[f[i][2]]]+b[i]+b[f[i][2]];
					if(j>=a[i]+a[f[i][2]]+a[f[i][1]])
						if(dp[j]<dp[j-a[i]-a[f[i][2]]-a[f[i][1]]]+b[i]+b[f[i][1]]+b[f[i][2]])
							dp[j]=dp[j-a[i]-a[f[i][2]]-a[f[i][1]]]+b[i]+b[f[i][1]]+b[f[i][2]];
				}
			}
		}
	}
	printf("%d\n",dp[n]);
	return 0;
}

 

发表新评论

© 2017 Powered by Typecho & Theme Quark