HDU 3586 Information Disturbing (二分+树形dp)

10-29 453 views

题意:给定一棵树,删除一些边,问所有叶子节点不与根节点相连的这些边的权值之和小于等于m的情况下的边的权值的最大值的最小值是多少。 思路:二分这个最大...
阅读全文 0

POJ 1947 Rebuilding Roads (树形背包)

10-26 881 views

题意:给定一棵树,问你最小删除多少个边,可以得到一个只函数k个节点的子树。 思路:d[i][j] 表示以i为根节点的子树中只存在j个节点的方法数。初始值 d[i][1...
阅读全文 0

Codeforces Round #322 (Div. 2) F. Zublicanes and Mumocrates(树形背包)

10-06 749 views

题意:给定一颗树,以不可能成为叶子的节点为根建树,把所有的节点分成两部分A,B。并且叶子节点各占一半,相邻的节点如果不同时属于一方,则删除,问最少删除...
阅读全文 0

HDU 4276 The Ghost Blows Light(树形dp,树上背包)

8-26 610 views

题意:给你一棵树,每条边上都有一个权值时间,每个节点也有一个权值。现在问你从1走到n,在规定的时间内,可以收获最大的权值是多少。 思路:最开始想这个题...
阅读全文 0

HDU 4274 Spy’s Work(树形dp)

8-26 426 views

题意:一颗以1为根节点的树,告诉你每个节点的子树的权值关系, 问你这个关系是否矛盾,每个节点的最小值为1。 思路:这个题明显的是区间上推问题,也就是说...
阅读全文 0

ZOJ 2315 New Year Bonus Grant(树形dp)

5-21 804 views

题意:给定一个树结构,每一个父节点如果发钱最多发给一个子节点。如果父节点有钱了就不能发给子节点。问最多能得多少钱。 思路:d[i][0]来表示第i个节点不接...
阅读全文 0

Codeforces Round #302 (Div. 1) D. Road Improvement(树形dp)

5-14 1,154 views

题意:给定一个无向图,要给没条路标记, 要么是0要么是1,问第i个点到其他所有的点最多只有一条是0的方案数。   树形dp,首先我们以1为根节点建为有根...
阅读全文 0

福州月赛 Problem F 检查站点(树形dp)

5-03 842 views

题意:汉语题面。。 思路:观察一下可以知道对于1的所有子节点,要使得路径最后,肯定是某一个子树走下去不用回到1,否则其他的一定要回到1, 继然要回到1的...
阅读全文 0

UVA 11307 – Alternative Arborescence(树形dp)

4-24 860 views

题意:相邻两个节点的颜色不同。用大于等于1的数对一棵树进行染色。 问最小的染色的值的和。 d[i][j] 来表示 第 i 个节点为 j 这个数值的时候 子树的最小值。...
阅读全文 0

UVA 1292 – Strategic game(水树形dp)

4-18 539 views

对于一个树,一个点只能覆盖相邻的边, 覆盖所有的边至少需要多少个点。 对于一个点。如果不覆盖他的话,那么他的所有节点都得覆盖。 对于一个点 如果覆盖他...
阅读全文 0
加载更多