2016年2月25日 星期四

[HOJ 297][NOIP 2010 提高組]引水入城 (題目備份)

HOJ生病惹QQ,因此在此悼念昔日光彩
題目備份,請參考~
題解在這裡
敬告:目前HOJ主機也許進入瀕死狀態了,常常無預警跳電。請看到這則公告的人能注意備份自己的資料,感謝。
至於主機壞掉以後會如何目前並沒有任何規劃.. 
Submit  Ranklist

Problem : 297 - 引水入城

Problem Statistics
Solved Member: 14  Submission: 148  User Tried: 14
Problem:


在一個遙遠的國度,一側是風景秀美的湖泊,另一側則是漫無邊際的沙漠。該國的行政區劃十分特殊,剛好構成一個N 行M 列的矩形,如上圖所示,其中每個格子都代表一座城市,每座城市都有一個海拔高度。

為了使居民們都盡可能飲用到清澈的湖水,現在要在某些城市建造水利設施。水利設施有兩種,分別為蓄水廠和輸水站。蓄水廠的功能是利用水泵將湖泊中的水抽取到所在城市的蓄水池中。因此,只有與湖泊毗鄰的第1行的城市可以建造蓄水廠。而輸水站的功能則是通過輸水管線利用高度落差,將湖水從高處向低處輸送。故一座城市能建造輸水站的前提,是存在比它海拔更高且擁有公共邊的相鄰城市,已經建有水利設施。

由於第N 行的城市靠近沙漠,是該國的干旱區,所以要求其中的每座城市都建有水利設施。

簡單的說你要在第一行選最少個城市建立蓄水廠,使得第N行的每個城市都能獲得水資源,當水資源能從城市A流往城市B,僅當城市A與城市B相鄰(上下左右),且城市A的海拔高度大於城市B的海拔高度。

那麼,這個要求能否滿足呢?如果能,請計算最少建造幾個蓄水廠;如果不能,求乾旱區中不可能建有水利設施的城市數目。
Input:
輸入的第一行是兩個正整數N 和M,表示矩形的規模。

接下來N 行,每行M 個正整數,依次代表每座城市的海拔高度。

測試資料編號能否滿足要求NM
1不能≤ 10≤ 10
2不能≤ 100≤ 100
3不能≤ 500≤ 500
4= 1≤ 10
5≤ 10≤ 10
6≤ 100≤ 20
7≤ 100≤ 50
8≤ 100≤ 100
9≤ 200≤ 200
10≤ 500≤ 500
Output:
輸出有兩行。

如果能滿足要求,輸出的第一行是整數1,第二行是一個整數,代表最少建造幾個蓄水廠。

如果不能滿足要求,輸出的第一行是整數0,第二行是一個整數,代表有幾座乾旱區中的城市不可能建有水利設施。
Sample Input:
Sample #1:
2 5
9 1 5 4 3
8 7 6 1 2

Sample #2:
3 6
8 4 5 6 4 4
7 3 4 3 3 3
3 2 2 1 1 2
Sample Output:
Sample #1:
1
1

Sample #2:
1
3
HINT:
Sample #1:
只需要在海拔為9 的那座城市中建造蓄水廠,即可滿足要求。

Sample #2:


上圖中,在3 個粗線框出的城市中建造蓄水廠,可以滿足要求。以這3 個蓄水廠為源頭。
在乾旱區中建造的輸水站分別用3 種顏色標出。當然,建造方法可能不唯一。
Source:
NOIP 2010 提高組
Problem Setter
hanhan0912
Testdata:
TestTimeMemoryScore
0-11000ms131072kb
0-21000ms131072kb
11000ms131072kb10
21000ms131072kb10
31500ms131072kb10
41000ms131072kb10
51000ms131072kb10
61000ms131072kb10
71000ms131072kb10
81000ms131072kb10
91000ms131072kb10
101000ms131072kb10

沒有留言:

張貼留言

歡迎留言或問問題~
若您的留言中包含程式碼,請參考這篇
如果留言不見了請別慌,那是因為被google誤判成垃圾留言,小莫會盡快將其手動還原