algorithm - 2010 ACM问题: CaSTLes的解决方案

Question

发布您的最佳解决方案!您可以在此处找到完整的问题描述和示例:ACM 2010 problems (pdf)

你有一组由道路相连的城堡，你想用最少的士兵征服所有的城堡。每个城堡都有三个属性:占领它所需的最少士兵人数、占领它会死亡的士兵人数以及必须留下来守住它的士兵人数。

任意两个城堡之间只有一条路径(道路形成一棵树)。你可以选择任何一座城堡作为第一个目标，但之后你必须沿着道路前行。一条路你只能走两次。你的机动部队必须保持一组。

Answer 1

我会这样解决:

暴力破解所有起始城堡(最多 100 个)对于每个起始城堡:填满数组

need[i] 和 cost[i] 意味着当你从选定的起点到 i，并试图征服从 i 开始的子树时，你至少需要 need[i] 焊料，而 cost[i] 焊料会死。

min_solder_to_attack_caSTLe[i] 来自输入文件。

显然，need[] 和 cost[] 值对于“终端”城堡来说是显而易见的。然后，对于已知所有“ child ”的 need[] 和 cost[] 值的每个城堡，您可以通过这种方式计算这座城堡的需求和成本:

成本[i] = 总和(成本[ child ])

获取 need[i] 是棘手的部分:我们知道它介于 max(min_solder_to_attack_caSTLe[all childs]) 和 max(min_solder_to_attack_caSTLe[all childs])+max(cost[all childs]) 之间。尝试所有变体将花费我们(number_of_childs)!并且可能是 n!，并且可能优化会在这里有所帮助，这是我现在停下来的地方。