HDU 1561&HDU 3449 一类简单依赖背包问题

HDU 1561。这道是树形DP了，所谓依赖背包，就是选A前必须选B，这样的问题。1561很明显是这样的题了。把0点当成ROOT就好，然后选子节点前必须先选根，所以初始化数组每一行为该根点的值。由于多选了0点，所以记得把m++.

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int MAXN=222;

int dp[MAXN][MAXN];

struct Edge{

	int u,v,next;

}edge[MAXN];

int head[MAXN],n,m,tot;

void addedge(int u,int v){

	edge[tot].u=u;

	edge[tot].v=v;

	edge[tot].next=head[u];

	head[u]=tot++;

}

void dfs(int u){

	for(int e=head[u];e!=-1;e=edge[e].next){

		int v=edge[e].v;

		dfs(v);

		for(int i=m;i>=1;i--){

			for(int k=1;k<i;k++){

				dp[u][i]=max(dp[u][i],dp[u][i-k]+dp[v][k]);

			}

		}

	}

}

int main(){

	int u,v;

	while(scanf("%d%d",&n,&m),n||m){

		m++;

		memset(dp,0,sizeof(dp));

		memset(head,-1,sizeof(head));

		tot=0;

		for(int i=1;i<=n;i++){

			scanf("%d%d",&u,&v);

			addedge(u,i);

			for(int k=1;k<=m;k++)

			dp[i][k]=v;

		}

		dfs(0);

		printf("%d\n",dp[0][m]);

	}

	return 0;

}

　　

HDU 3449.。也是这样的题目，选物品前先买盒子。那么设dp[i][j]为前i个盒子钱为j下最优值。把每个盒子情况当成0/1背包来看。由于先买了盒子，所以初始化时是i-1情况下j-p的最优值。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

int dp[52][100050];

int main(){

	int n,w,p,k,wi,vi;

	while(scanf("%d%d",&n,&w)!=EOF){

		memset(dp,0,sizeof(dp));

		for(int i=1;i<=n;i++){

			scanf("%d%d",&p,&k);

			for(int j=p;j<=w;j++){

				dp[i][j]=dp[i-1][j-p];

			}

			for(int kk=1;kk<=k;kk++){

				scanf("%d%d",&wi,&vi);

				for(int j=w;j>=wi+p;j--){

					dp[i][j]=max(dp[i][j],dp[i][j-wi]+vi);

				}

			}

			for(int j=0;j<=w;j++)

			dp[i][j]=max(dp[i][j],dp[i-1][j]);

		}

		printf("%d\n",dp[n][w]);

	}

	return 0;

}