渡轮问题Ship

题目描述
Palmia河从东往西流过Palmia国，把整个国家分成南北两半。河的两岸各有N个城市，北岸的每一个城市都与南岸的一个城市互为友好城市，而且任意两个北岸城市的友好城市都不相同。每一对友好城市都向政府申请，希望开通一条连接两城市的航线。但政府遇到一个问题：Palmia河上经常有大雾，这对航行不利。为了降低出现航行事故的可能性，政府决定任意两条航线不能交叉，这样，政府就不一定能接受所有城市的申请。你的任务是：写一程序帮助政府决定接受哪些城市的申请，使开通的航线最多。输入输出格式输入格式：输入数据文件Ship.in，第一行有两个整数，第一个整数代表Palmia河河岸线的长度（≤10000），第二个整数代表Palmia河的宽度（≤50）。第二行有一个整数N（≤1000），表示河一侧的城市数目；以下N行每行有两个非负整数C、D，C代表北岸城市的位置（Palmia河从西边国界开始到该城市的距离），D代表南岸城市的位置，C和D为一对友好城市。输出格式：输出到Ship.out，它只有一个整数，为可以获得的最大航线数目。输入输出样例输入样例#1：Ship.in30 4
7
22 4
2 6
10 3
15 12
9 8
17 17
4 2输出样例#1：Ship.out4思路将两岸的城市位置按任意一岸城市位置排序，再求出另外一岸城市位置的最长不下降子数列的长度即可。代码#include<stdio.h>
int a[1001],b[1001][2]={1};
int main（）
{int c,d,n,i,j,p;
scanf（"%d%d%d",&c,&d,&n）;
for（i=1;i<=n;i++）
{
scanf（"%d%d",&a[i],&b[i][1]）;
b[i][2]=1;
}
for（i=1;i<=n-1;i++）
for（j=1;j<=n-i;j++）
if（a[j]>a[j+1]）
{
p=a[j];
a[j]=a[j+1];
a[j+1]=p;
b[0][1]=b[j][1];
b[j][1]=b[j+1][1];
b[j+1][1]=b[0][1];
}
p=0;
for（i=1;i<=n;i++）
for（j=i+1;j<=n;j++）
{
if（b[i][1]<b[j][1]&&b[i][2]>=b[j][2]）
b[j][2]=b[i][2]+1;
if（b[j][2]>p）
p=b[j][2];
}
printf（"%d",p）;
return 0;
}本文永久更新链接地址：http://www.linuxidc.com/Linux/2016-03/129178.htm