题解 P2782 【友好城市】

· · 题解

【算法分析】

我们将每对友好城市看成一条线段，则这道题的描述化为：有N条线段，问最少去掉多少条线，可以使剩下的线段互不交叉？

第一，以北岸为线的起点而南岸为线的终点；先将所有的线按照起点坐标值从小到大排序，按照每条线的终点坐标计算交叉数：求线I的交叉数A[I]，则检查所有1..I-1条线，若线J( 1<= J< I)的终点值大于线I的终点值，则线I与线J相交。A[I]与A[J]同时加1。整个搜索量最大为5000*5000。

第二，将A数组从大到小排序，每删除一条线，则将与之相交的线的A值减1，重复这个过程，直到所有A值都为0。此时剩下的线则全不交叉。

此时，1、2、3航线的交叉数都一样，如果删去的是3、5线，则剩下的1、2、4线互不相交，最多航线数为3；但如果删去的是2、3，则还要删去第5线才符合要求，此时的最多航线数为2，不是最优解。

于是，我们从上面的分析中再深入，将航线按起点坐标排好序后，如上所述，在本题中，只要线J的起点小于线I的起点，同时它的终点也小于线I的终点，则线J和线I不相交。因此，求所有线中最多能有多少条线不相交，实际上是从终点坐标值数列中求一个最长不下降序列。这就把题目转化为一个非常典型的动态规划题目了。

求最长不下降序列的规划方程如下：

 L(Si)=max{L(Sj)}+1；1< = j < i且 Sj < Si。Si为航线的终点坐标值。

从以上分析过程可以得出：当我们拿到一道题时，不要急于求解，而应先将题目的表面现象一层层象剥竹笋一样去掉，只留下最实质的内容。这时再来设计算法，往往能事半功倍。