题目描述
有一条横贯东西的大河,河有笔直的南北两岸,岸上各有位置各不相同的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;
}
我把作者写的看了一下,我改了一下加工了一下,我把多余不要的东西删掉了,其他的思路上面时一致的
标签:060,max1,容量,友好城市,城市,深入浅出,int,swap From: https://blog.csdn.net/2301_80550438/article/details/140765768