转贴，帮人问 BOI 題目請教 boi.tasks.1.gems
转贴，帮人问
BOI 題目請教
在这里先问一题 BOI 的题目。
(http://www.ut.ee/boi/?item=boi.tasks.1.gems)
有一家珠宝生产公司，要在一棵树 (图论中的树) 上装上珠宝。每颗不同的珠宝都会有不同的价钱──即是没有两颗不同的珠宝是相同价钱的。为了令到那棵树更具吸引力，厂商要求两个连着的节点必须用不同的珠宝。现在给予那棵树的结构，试编程找出要装饰这棵树的最便宜的价钱。
这题应该是一题无根树动规，递归方程我写过的了，但是有一点不肯定。所以我有两个问题想请教：
1. 是不是我随便抽一个节点当作根，再作动规，出来的一定是最优解？
2. 对于每个节点，我都需要记着两个对于该节点的最优解，但如何决定一个节点的两个最优解？会不会遇着两个最优解都不能符合题目要求的情况？
谢谢大家！
问题点数：0、回复次数：3Top
1 楼wchzw（魔索剑扬）回复于 2005-06-04 14:15:49 得分 0
天那,oi题还是去大榕树问吧Top
2 楼mostideal（三甲）回复于 2005-06-04 14:22:25 得分 0
我是只能帮顶了。。Top
3 楼wasltone（WT.）回复于 2005-06-04 19:43:56 得分 0
UP，如果解出再+100分Top
