1012 友好城市（转化-最长上升子序列问题）

ゝ一纸荒年。 2022-09-11 13:12 244阅读 0赞

**1. 问题描述：**

Palmia国有一条横贯东西的大河，河有笔直的南北两岸，岸上各有位置各不相同的N个城市。北岸的每个城市有且仅有一个友好城市在南岸，而且不同城市的友好城市不相同。每对友好城市都向政府申请在河上开辟一条直线航道连接两个城市，但是由于河上雾太大，政府决定避免任意两条航道交叉，以避免事故。编程帮助政府做出一些批准和拒绝申请的决定，使得在保证任意两条航线不相交的情况下，被批准的申请尽量多。

**输入格式**

第1行，一个整数N，表示城市数。第2行到第n+1行，每行两个整数，中间用1个空格隔开，分别表示南岸和北岸的一对友好城市的坐标。

**输出格式**

仅一行，输出一个整数，表示政府所能批准的最多申请数。

**数据范围**

1 ≤ N ≤ 5000，  
0 ≤ xi ≤ 10000

**输入样例：**

7  
22 4  
2 6  
10 3  
15 12  
9 8  
17 17  
4 2

**输出样例：**

4  
来源：[https://www.acwing.com/problem/content/1014/][https_www.acwing.com_problem_content_1014]

**2. 思路分析：**

首先需要读懂题目的意思，现在南北岸各有位置不同的城市，并且南岸与北岸都有一个与之配对的城市（友好城市），我们需要在这些友好城市上建设航线，并且求解在不相交的前提下最多能够创建航线的数目。我们可以先画画图，找一下规律，可以发现当我们对下图中的第一行的坐标从小到大排序之后那么第二行的坐标可以对应第一行的坐标从而找到合法的方案，可以发现排序之后如果第二行的坐标出现了逆序的情况那么这两条航线肯定是相交的，所以当我们排序之后问题就转化为了求解最长上升子序列的问题，只有当这些坐标按照上升的顺序排列那么所有的航线才不会相交；其实想到排序这一点很重要（问题的转化），我们只有在平时多做题积累这样的经验，当我们遇到类似的题目才会联想到某些处理方案然后试一下行不行。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_10_color_FFFFFF_t_70_g_se_x_16][]

**3. 代码如下：**

if __name__ == '__main__':
        n = int(input())
        a = list()
        dp = [0] * n
        # 转化为元组进行排序
        for i in range(n):
            x, y = map(int, input().split())
            a.append((x, y))
        a.sort(key=lambda x: (x[0], x[1]))
        # 求解最长公共子序列
        res = 0
        for i in range(n):
            dp[i] = 1
            for j in range(i):
                # 因为是对第一维进行排序所以需要我们需要在第二维中找最长上升子序列反之如果对第二维进行排序那么就需要在第一维中找最长上升子序列, 这两者是一一对应的
                if a[i][1] > a[j][1]:
                    dp[i] = max(dp[i], dp[j] + 1)
                res = max(res, dp[i])
        print(res)

if __name__ == '__main__':
        n = int(input())
        a = list()
        dp = [0] * n
        # 转化为元组进行排序
        for i in range(n):
            x, y = map(int, input().split())
            a.append((x, y))
        a.sort(key=lambda x: (x[1], x[0]))
        # 求解最长公共子序列
        res = 0
        for i in range(n):
            dp[i] = 1
            for j in range(i):
                if a[i][0] > a[j][0]:
                    dp[i] = max(dp[i], dp[j] + 1)
                res = max(res, dp[i])
        print(res)

[https_www.acwing.com_problem_content_1014]: https://www.acwing.com/problem/content/1014/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_10_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/38179789d31a41ab81beb68163f1953e.png