web analytics

Category Archives: 树形DP

树形依赖背包裸题

题目:有一个树,每一个节点代表一个物品,每个物品有重量和价值,每个物品必须先选父亲才能选自己。求给定重量内最大价值。
[......]

阅读全文

POJ 1344 Tree Size Problem 树形DP

题目链接:http://poj.org/problem?id=1344
[......]

阅读全文

战略游戏 树形DP

描述
Bob喜欢玩电脑游戏,特别是战略游戏。但是他经常无法找到快速玩过游戏的办法。现在他有个问题。他要建立一个古城堡,城堡中的路形成一棵树。他要在这棵树的结点上放置最少数目的士兵,使得这些士兵能了望到所有的路。注意,某个士兵在一个结点上时,与该结点相连的所有边将都可以被了望到。 请你编一程序,给定一树,帮Bob计算出他需要放置最少的士兵。

[......]

阅读全文

NOIP2014联合权值-树形DP

题目描述 Description
无向连通图G 有n 个点,n – 1 条边。点从1 到n 依次编号,编号为 i 的点的权值为W i ,每条边的长度均为1 。图上两点( u , v ) 的距离定义为u 点到v 点的最短距离。对于图G 上的点对( u, v) ,若它们的距离为2 ,则它们之间会[......]

阅读全文

poj1947-Rebuilding Roads[树形DP]

poj 不能用bits也是很绝望啊。

Rebuilding Roads
Time Limit: 1000MS Memory Limit: 30000K
Total Submissions: 11612 Accepted: 5329
Description

The cows have[......]

阅读全文