歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

渡輪問題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;
}

Copyright © Linux教程網 All Rights Reserved