[POJ1155]TELE
试题描述
输入
输出
输入示例
9 6 3 2 2 3 2 9 3 2 4 2 5 2 3 6 2 7 2 8 2 4 3 3 3 1 1
输出示例
5
数据规模及约定
见“输入”；另：过程中不会有超过 int 的值。
题解
树形 dp（树上背包）。
设 f(i, j) 表示子树 i 中选择了 j 个叶子的最大获利（若为负则 -f(i, j) 为最小亏损）。那么答案就是最大的 j，满足 f(i, j) 非负。
考虑子树 u，儿子上的信息肯定是最有子结构，所以先算出所有的 f(son, j)，然后分别将一个个子树的信息加入 f(i, j)（f(u, i+j) = max{ f(u, i) + f(son, j) - dist(i, son) | j > 0 , f(u, i) + f(son, j) | j = 0 }）。
可以证明总转移数是 O(n2) 级别的，详见这里。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;
const int BufferSize = 1 << 16;
char buffer[BufferSize], *Head, *Tail;
inline char Getchar() {
if(Head == Tail) {
int l = fread(buffer, 1, BufferSize, stdin);
Tail = (Head = buffer) + l;
}
return *Head++;
}
int read() {
int x = 0, f = 1; char c = Getchar();
while(!isdigit(c)){ if(c == ‘-‘) f = -1; c = Getchar(); }
while(isdigit(c)){ x = x * 10 + c - ‘0‘; c = Getchar(); }
return x * f;
}
#define maxn 3010
#define oo 2147483647
int n, usr, m, head[maxn], nxt[maxn], to[maxn], dist[maxn], pay[maxn];
void AddEdge(int a, int b, int c) {
to[++m] = b; dist[m] = c; nxt[m] = head[a]; head[a] = m;
return ;
}
int f[maxn][maxn], clea[maxn];
void dp(int u) {
if(u > n - usr) {
clea[u] = 1;
f[u][0] = 0; f[u][1] = pay[u];
return ;
}
f[u][0] = 0;
for(int e = head[u]; e; e = nxt[e]) {
dp(to[e]);
for(int i = clea[u]; i >= 0; i--) if(f[u][i] < oo)
for(int j = 0; j <= clea[to[e]]; j++) if(f[to[e]][j] < oo)
f[u][i+j] = max(f[u][i+j], f[u][i] + f[to[e]][j] - (j ? dist[e] : 0));
clea[u] += clea[to[e]];
}
return ;
}
int main() {
n = read(); usr = read();
for(int i = 1; i <= n - usr; i++) {
int k = read();
while(k--) {
int u = read(), c = read();
AddEdge(i, u, c);
}
}
for(int i = n - usr + 1; i <= n; i++) pay[i] = read();
for(int i = 1; i <= n; i++)
for(int j = 0; j <= n; j++) f[i][j] = -oo;
dp(1);
for(int j = clea[1]; j; j--) if(f[1][j] >= 0) return printf("%d\n", j), 0;
puts("0");
return 0;
}
原文：http://www.cnblogs.com/xiao-ju-ruo-xjr/p/7309030.html