树形DP做题记录

“访问”美术馆

树形背包问题。容易将美术馆转化成一棵二叉树，将展厅也视为走廊，每个走廊对应二叉树上一个节点。对于这种读入方式可以采用递归建树。

记 \(t_{cost}\) 为通过这个走廊所需的时间，记 \(t_{val}\) 为可以拿到的最多的画，记 \(dp_{i,j}\) 表示在第 \(i\) 个走廊用时 \(j\) 可以拿到的最多的画。

对于每个叶子节点，即展厅，从 \(1 \sim t_{val}\) 枚举拿画需要的时间 \(tim\)，因此有

对于非叶子节点，用花费在左右儿子的时间来转移状态。对于当前可用的时间 \(tim\)，有

因此可以得到转移方程

最后的结果为 \(dp_{1,n-1}\)。

需要注意的点有：
·警察到达就算结束，给的 \(n\) 需要减一
·对于每条走廊走过去还要回来，因此耗费的时间要乘二

#include<bits/stdc++.h>
#define int long long
#define MAX 1110
using namespace std;

inline int read()
{
	int s=0,w=1;
	char c=getchar();
	while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
	while(isdigit(c)) s=(s<<1)+(s<<3)+(c^48),c=getchar();
	return s*w;
}

int n,m;
int x;

struct edge
{
	int nex,to;
}e[MAX<<1];
int head[MAX],cnt;
inline void add(int x,int y)
{
	e[++cnt].nex=head[x];
	head[x]=cnt;
	e[cnt].to=y;
	return;
}

int dp[MAX][MAX];    //dp_{i,j}  第i个走廊用时j获得的最大量 
struct Tree
{
	int cost,val;
}t[MAX];
void build(int now)
{
	t[now].cost=read(),t[now].val=read();
	t[now].cost<<=1;
	if(t[now].val) return;
	build(now<<1),build(now<<1|1);
}
void dfs(int now)
{
	if(t[now].val)
	{
		for(int tim=0;tim+t[now].cost<=n;++tim)
		{
			if(tim/5>t[now].val) break;
			dp[now][t[now].cost+tim]=tim/5;
		}
		return;
	}
	dfs(now<<1);	
	dfs(now<<1|1);
	for(int tim=t[now].cost;tim<=n;++tim)
		for(int ltim=0;ltim+t[now].cost<=tim;++ltim)
		{
			int rtim=tim-ltim-t[now].cost;
			dp[now][tim]=max(dp[now][tim],dp[now<<1][ltim]+dp[now<<1|1][rtim]);
		}
	return;
}

signed main()
{
	n=read(); --n;
	build(1);
	dfs(1);
	cout<<dp[1][n];
	return (0-0);
}

原文地址：http://www.cnblogs.com/LittleTwoawa/p/16793626.html