Description

某市的M公園中有一個近乎圓形的湖，有100個主要景點分布在湖邊，為了方便游客，公園在一些景點之間開設(shè)了直通的摩托飛艇擺渡的項目一來減少游客在景點到景點之間所花的時間，二來也可以讓游客體驗一下驚險刺激的摩托飛艇。果然摩托飛艇擺渡項目大為成功，為了充分滿足游客需要，擺渡線路越來越多。不料隨著線路的增加，危險性也隨之增加。如果兩個擺渡線路之間有交叉（如上圖），在這兩個線路上的飛艇一旦發(fā)生碰撞，后果將不堪設(shè)想。

公園的管理層近日做出決定，本著安全第一的原則，在這個湖上取消一些線路，使剩下的任意兩條線路在行駛階段（即不考慮碼頭）不交叉。同時，考慮到經(jīng)濟效益，他們要求被取消的線路數(shù)最小，即保留盡量多的線路。他們希望你能夠幫助他們算一算最多可以保留多少條線路。

Input

從文件line.in中讀入數(shù)據(jù)，文件的第一行為N（1=

Output

將結(jié)果輸出到文件line.out，文件只有一行，只有一個數(shù)，就是保留下來的線路的最多條數(shù)。

Sample Input
5
91　31
1　45
27　5
11　65
43　72

Sample Output
3

.
.
.
.
.
.
分析
本題的思路是使用floyd來計算最大保留邊，f[i,j]表示i區(qū)間到j(luò)區(qū)間內(nèi)最大保留邊，方程：f[i,j]:=max(f[i,k]+f[k,j]+t,f[i,j]);(t為i,j之間是否存在邊)
我們從i開始枚舉，用i+l，也就是j(l是到下一個區(qū)間的距離)來更新各個點
因為i到j(luò)區(qū)間不可能只有這兩個點，故用k來枚舉i~j的各個點
最后在數(shù)組內(nèi)找出最大保留邊，并輸出即可

.
.
.
.
.
程序：

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std;int main() {int n,f[205][205];memset(f,0,sizeof(f));scanf("%d",&n);for(int i=1;i<=n;i++){int x,y;scanf("%d%d",&x,&y);if (x>y) swap(x,y);f[x][y]=f[x+100][y+100]=1;}int ans=0;for (int l=2;l<=100;l++)for (int i=1;i<=200-l-1;i++){int a=i,b=i+l-1,t=0;for (int k=a+1;k<=b-1;k++)t=max(t,f[a][k]+f[k][b]);f[a][b]+=t;ans=max(ans,f[a][b]);}printf("%d",ans);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/YYC-0304/p/11094923.html

總結(jié)

以上是生活随笔為你收集整理的摆渡线路的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。