首頁資訊【9930】友好城市

【9930】友好城市

來源：泰然健康網(wǎng) 時間：2024年11月25日 19:16

Time Limit: 1 second
Memory Limit: 128 MB

【問題描述】

Palmia國有一條橫貫東西的大河，河有筆直的南北兩岸，岸上各有位置各不相同的N個城市。北岸的每個城市有且僅有一個友好城
市在南岸，而且不同城市的友好城市不相同。
每對友好城市都向政府申請?jiān)诤由祥_辟一條直線航道連接兩個城市，但是由于河上霧太大，政府決定避免任意兩條航道交
叉，以避免事故。編程幫助政府做出一些批準(zhǔn)和拒絕申請的決定，使得在保證任意兩條航線不相交的情況下，被批準(zhǔn)的申請盡
量多。

【輸入格式】

第1行，一個整數(shù)N(1<=N<=5000)，表示城市數(shù)。
第2行到第n+1行，每行兩個整數(shù)，中間用1個空格隔開，分別表示南岸和北岸的一對友好城市的坐標(biāo)。(0<=xi<=10000)

【輸出格式】

僅一行，輸出一個整數(shù)，政府所能批準(zhǔn)的最多申請數(shù)。

Sample Input

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

Sample Output

【題解】

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

這些信息可以看成線。

假設(shè)有i<j；

且j的另外一端為xj，i的另外為xi。如果xi>xj。則這兩條線會有交點(diǎn)。

這個時候我們可以把南岸的n個數(shù)字看成是1..n;

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

南岸1..n是a數(shù)組的下標(biāo)i

則我們要從1..n中選幾個數(shù)字。滿足

當(dāng)i<j時a[j] > a[i](如果不滿足就會有交點(diǎn)。)，然后要使得數(shù)字的數(shù)目最大。

這就是一個最長不下降子序列的問題了。

設(shè)m[i]為以i為序列的最后一個數(shù)字的最長不下降子序列的長度。

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) //表示以南岸為關(guān)鍵字升序排return 1;return 0; } int main() {//freopen("F:rush.txt","r",stdin);scanf("%d",&n);for (int i =1;i <= n;i++) //先把線以南岸為關(guān)鍵字排序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; }

網(wǎng)址: 【9930】友好城市 http://m.u1s5d6.cn/newsview89072.html