问题 E: 深入浅出学算法060-友好城市

题目描述

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

输入

第1行，一个整数N，表示城市数。

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

输出

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

样例输入 Copy

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

样例输出 Copy

4

提示

50% 1<=N<=5000,0<=xi<=10000

100% 1<=N<=2e5,0<=xi<=1e6

哎我写的放在下面了，大家想要的自行复制获取

#include<iostream>
#include<algorithm>
using namespace std;
int a[10001][3];
int b[10001][4];
int main()
{
    int n;
    cin >> n;
    //输入每个友好型城市到数组里面
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i][1] >> a[i][2];
    }
    //把头数小的放前面依次排序，swap是交换两数大小
    for (int i = 1; i <= n; i++)
    {
        for (int j = i + 1; j <= n; j++)
        {
            if (a[j][1] < a[i][1])
            {
                swap(a[i][1], a[j][1]);
                swap(a[i][2], a[j][2]);
            }
        }
    }
    //这里开始处理b数组里的数据，第一个放a数组中的后值，第二个放目前到该数的能容量的最大线路数
    for (int i = 1; i <= n; i++)
    {
        b[i][1] = a[i][2];
        b[i][2] = 1;
    }
    //此处开始动态规划，
    for (int i = n - 1; i >= 1; i--)
    {
        int max1 = 0;
        //max用来记录放新的线路时是否是按照最大的容量来放的，具体自己理解
        for (int j = i + 1; j <= n; j++)
        {
            //从当前数开始如果有比我大的，那么能容量的就多1，并且记录max1为当前最大容量
            if (b[j][1] >= b[i][1] && b[j][2] > max1)
            {
                max1 = b[j][2];
            }
        }
        if (max1 > 0)
        {
            b[i][2] = max1 + 1;
        }
    }
    int k = 1;
    //此处寻找最大值
    for (int i = 1; i <= n; i++)
    {
        if (b[i][2] > b[k][2])
        {
            k = i;
        }
    }
    cout << b[k][2] << endl;
    return 0;
}

我把作者写的看了一下，我改了一下加工了一下，我把多余不要的东西删掉了，其他的思路上面时一致的

参考文献：1169. 【动态规划】友好城市-CSDN博客