18 Apr 10 武汉大学第八届程序设计竞赛部分决赛题目分析

在这里简单说一些我出的题目。

F: Pie

此题很明显的是一个最小匹配的模型。而后根据题目数据的特点可以利用DP来解决。

简单说一下性质：

1. 排序之后的匹配是不存在交叉线的。也就是说，如果第i高的男的和第j高的女的匹配，那么比i矮的男的就不能和比j高的女的匹配。同理，比i高的男的也就不能和比j矮的女的匹配。

2. 题目里有说男女的人数相差不到100，所以我们可以知道一个人的的可选匹配数量最多是100个。再加上这个性质，我们就可以用O(n * 100) = O(1000000)的DP来解决这个问题。相关的实现要用到滚存。

附上代码： (more…)

05 Apr 10 WHU2010校赛预赛B题：fix

题目意思是告诉很多点（最多18个），然后有一些点是固定住了的，有一些点是没有固定的。现在需要用小木棍连接，使得所有的点都固定住。

问小木棍的总长度最短是多少。

这个题目是我出的，在这里说一下这个题目的做法： (more…)