P1064 金明的预算方案

P1064 金明的预算方案

存在依赖关系背包转化分组背包。

题意

给定 $n$ 个物品的价值和体积，他们之间存在简单的依赖关系，即一个结点要么是父亲结点，要么是儿子结点，且一个父亲结点最多有两个儿子结点。

Sol

我们考虑对于一个父亲结点，他要么不选取儿子结点，要么选取一个儿子结点，要么选取两个儿子结点，此时共有 $4$ 种方案，仅可能选取其中 $1$ 种方案。并且不存在结点使得既为父亲结点，又为儿子结点，那么转化成分组背包。

#include<bits/stdc++.h>
using namespace std;

template <typename T>
inline T read(){
	T x=0,f=1;char c=getchar();
	while(!isdigit(c)){	if(c=='-') f=-f;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}

#define lint long long int
#define ulint unsigned lint
#define readint read<int>()
#define readlint read<lint>()
const int inf=1e9+1e7,MAXN=5e4+1e1;
const lint INF=1e18+1e9;

struct Node{
	int w,v;
}Set[MAXN][4];
int dp[MAXN],son[MAXN][4],fa[MAXN],w[100],v[100],n,m;

int main(void){

	scanf("%d%d",&m,&n);
	for(int i=1;i<=n;i++){
		v[i]=readint,w[i]=v[i]*readint;
		int u=readint;
		if(son[u][0]) son[u][1]=i;
		else son[u][0]=i;
		fa[i]=u;
	}
	for(int i=1;i<=n;i++) if(!fa[i]){
		Set[i][0]=(Node){w[i],v[i]};
		Set[i][1]=(Node){w[i]+w[son[i][0]],v[i]+v[son[i][0]]};
		Set[i][2]=(Node){w[i]+w[son[i][1]],v[i]+v[son[i][1]]};
		Set[i][3]=(Node){w[i]+w[son[i][0]]+w[son[i][1]],v[i]+v[son[i][0]]+v[son[i][1]]};
	}
	for(int i=1;i<=n;i++) for(int j=m;j;j--) for(int k=0;k<4;k++){
		int W=Set[i][k].w,V=Set[i][k].v;
		if(j>=V) dp[j]=max(dp[j-V]+W,dp[j]);
	}
	printf("%d\n",dp[m]);

	return 0;
}