Palmia國(guó)有一條橫貫東西的大河,河有筆直的南北兩岸,岸上各有位置各不相同的N個(gè)城市。北岸的每個(gè)城市有且僅有一個(gè)友好城市在南岸,而且不同城市的友好城市不相同。
每對(duì)友好城市都向政府申請(qǐng)?jiān)诤由祥_(kāi)辟一條直線航道連接兩個(gè)城市,但是由于河上霧太大,政府決定避免任意兩條航道交叉,以避免事故。編程幫助政府做出一些批準(zhǔn)和拒絕申請(qǐng)的決定,使得在保證任意兩條航線不相交的情況下,被批準(zhǔn)的申請(qǐng)盡量多。
第1行,一個(gè)整數(shù)N(1≤N≤5000),表示城市數(shù)。
第2行到第n+1行,每行兩個(gè)整數(shù),中間用1個(gè)空格隔開(kāi),分別表示南岸和北岸的一對(duì)友好城市的坐標(biāo)。(0≤xi≤10000)
7 22 4 2 6 10 3 15 12 9 8 17 17 4 2
4
這部分是關(guān)于1月23日,聶老師講解的關(guān)于動(dòng)態(tài)規(guī)劃的練習(xí)題目,大家可以通過(guò)練習(xí)題檢驗(yàn)一下聽(tīng)講的效果