zju2280 -- key to freedom.cpp

Zhejiang University Online Judge 第2277题至第2283题的代码和解题报告

// PROB         Zju Online Judge 2280 -- Key to Freedom
// Algorithm    Tree DP
// Complexity   O (n^3)
// Author       LoveShsean
#include <stdio.h>
#include <vector>

#define maxn 110

using namespace std;

int n, power;
int cost [maxn], key [maxn], mk [maxn];
int opt [maxn] [maxn];
int ls [maxn], rs [maxn];
int ans;

vector <int> g [maxn];

bool init ()
{
 	int i, x, y;
 	if (scanf ("%d%d", &n, &power) != 2) return 0;
 	for (i = 1; i <= n; i ++)
 		scanf ("%d%d", cost + i, key + i), g [i].clear ();
 	for (i = 1; i < n; i ++)
 		scanf ("%d%d", &x, &y), g [x].push_back (y), g [y].push_back (x);
 	return 1;
}

void build_tree (int u, int p)
{
 	vector <int> :: iterator Iter;
 	int v;
 	for (Iter = g [u].begin (); Iter != g [u].end (); Iter ++)
 	{
 	 	v = *Iter;
 	 	if (v == p) continue;
 	 	rs [v] = ls [u];
 	 	ls [u] = v;
 	 	build_tree (v, u);
 	}
}

int search (int p, int power)
{
 	if (p == 0) return 0;
 	if (power < 0) return 0;
 	if (opt [p] [power] >= 0) return opt [p] [power];
 	int max = search (rs [p], power), j, r, s;
 	for (j = 0; j <= power - cost [p]; j ++)
 	{
 		r = search (ls [p], j); s = search (rs [p], power - cost [p] - j);
 		if (key [p] + r + s > max) max = r + s + key [p];
 	}
 	return opt [p] [power] = max;
}

int main ()
{
 	while (init ())
 	{
 	 	memset (ls, 0, sizeof (ls));
 	 	memset (rs, 0, sizeof (rs));
 	 	build_tree (1, 0);
 	 	memset (opt, 0xff, sizeof (opt));
 	 	if (power < cost [1]) ans = 0;
 	 	else ans = search (ls [1], power - cost [1]) + key [1];
 	 	printf ("%d\n", ans);
 	}
 	return 0;
}