我肝了好久……

题目描述

经过数月的精心准备，Peer Brelstet，一个出了名的盗画者，准备开始他的下一个行动。艺术馆的结构，每条走廊要么分叉为两条走廊，要么通向一个展览室。Peer知道每个展室里藏画的数量，并且他精确测量了通过每条走廊的时间。由于经验老到，他拿下一幅画需要5秒的时间。你的任务是编一个程序，计算在警察赶来之前，他最多能偷到多少幅画。

样例的图……

原题链接

Slove

树形DP-树形背包
mon[i]到节点i的用时
十年DP推方程

1. 设计状态：d[i][j]，以i为根节点，取画j副时的最少用时。
2. 边界：d[i][j]=j*5,(i为展室，0<=j<=该展室画数）
3. 转移方程：d[u][j]=min(d[u][j],d[u][j-k]+d[v][k]+mon[v]).（u到v有边；j为u的最大画数）
4. 按照最大画幅，倒序枚举，用时低于S的就是答案。

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#define N 1010
using namespace std;
int s;
int tree[N*10];
int mon[N],vl[N],cnt;
int d[N][N];
int sz[N],sum;
int first[N],nxt[N],to[N],len;
void add(int u,int v){
	to[++len]=v;
	nxt[len]=first[u];
	first[u]=len;
}
void infs(int u){
	mon[u]=mon[u]*2;
	if(vl[u]){
		sum+=vl[u];
		for(int i=0;i<=vl[u];i++) d[u][i]=i*5;
		return ;
	}
	scanf("%d%d",&mon[u*2],&vl[u*2]);
	add(u,u*2);infs(u*2);
	scanf("%d%d",&mon[u*2+1],&vl[u*2+1]);
	add(u,u*2+1),infs(u*2+1);
}
void dfs(int u){
	if(vl[u]){
		sz[u]=vl[u];
		return ;
	}
	for(int i=first[u];i!=-1;i=nxt[i]){
		dfs(to[i]);
		sz[u]+=sz[to[i]];
		for(int j=sz[u];j>=0;j--){
			for(int k=min(j,sz[to[i]]);k>=0;k--) d[u][j]=min(d[u][j],d[u][j-k]+d[to[i]][k]+mon[to[i]]);
		}
	}
}
int main()
{
	memset(first,-1,sizeof(first));
	for(int i=0;i<=1001;i++) for(int j=1;j<=1001;j++) d[i][j]=30000;
	scanf("%d",&s);
	s--;
	add(0,1);
	scanf("%d%d",&mon[1],&vl[1]);
	infs(1);
	dfs(0);
	for(int i=sum;i>=0;i--){
		if(d[0][i]<s){
			printf("%d",i);
			return 0;
		}
	}
	return 0;
}