首页 > 资讯 > 【9930】友好城市

【9930】友好城市

泰然健康网
2024-11-25 19:16

Time Limit: 1 second
Memory Limit: 128 MB

【问题描述】

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

【输入格式】

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

【输出格式】

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

Sample Input

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

Sample Output

【题解】

首先把这些友好城市的信息。按照南岸的序号大小升序排列。

这些信息可以看成线。

假设有i<j；

且j的另外一端为xj，i的另外为xi。如果xi>xj。则这两条线会有交点。

这个时候我们可以把南岸的n个数字看成是1..n;

然后北岸的位置是a[i]的值。

南岸1..n是a数组的下标i

则我们要从1..n中选几个数字。满足

当i<j时a[j] > a[i](如果不满足就会有交点。)，然后要使得数字的数目最大。

这就是一个最长不下降子序列的问题了。

设m[i]为以i为序列的最后一个数字的最长不下降子序列的长度。

m[i]初值为1

for (int i = 2;i <= n;i++)

for (int j = 1;j <= i-1;j++)

if(a[i] > a[j] && f[i] < f[j]+1)

f[i] = f[j]+1;

最后在1..n中找最大值f[k]

【代码】

#include <cstdio> #include <algorithm> using namespace std; struct data {int a,b; }; int n,m[5010]; data city[5010]; int cmp(const data &a,const data &b) {if (a.a < b.a) //表示以南岸为关键字升序排return 1;return 0; } int main() {//freopen("F:rush.txt","r",stdin);scanf("%d",&n);for (int i =1;i <= n;i++) //先把线以南岸为关键字排序scanf("%d%d",&city[i].a,&city[i].b);sort(city+1,city+1+n,cmp);for (int i = 1;i <= n;i++)m[i] = 1;for (int i = 2;i <= n;i++)for (int j = 1;j <= i-1;j++) //city[1..n].b就是北岸的各个位置if (city[i].b>city[j].b && m[i] < m[j]+1) //求其最长不下降子序列m[i] = m[j] + 1;int tm = m[1];for (int i = 2;i <= n;i++) //求出f[1..n]中的最大值并输出if (m[i] > tm)tm = m[i];printf("%d",tm);return 0; }