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

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

F: Pie

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

简单说一下性质：

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

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

附上代码： (more…)