渡轮问题Ship

渡轮问题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.in

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

输出样例#1：

Ship.out

4

思路

将两岸的城市位置按任意一岸城市位置排序，再求出另外一岸城市位置的最长不下降子数列的长度即可。

代码

#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;
}

本文永久更新链接地址：