codevs 1066 引水入城

題目描述 Description

在一個遙遠的國度，一側是風景秀美的湖泊，另一側則是漫無邊際的沙漠。該國的行政 區劃十分特殊，剛好構成一個N行M列的矩形，如上圖所示，其中每個格子都代表一座城 市，每座城市都有一個海拔高度。 為了使居民們都盡可能飲用到清澈的湖水，現在要在某些城市建造水利設施。水利設施 有兩種，分別為蓄水廠和輸水站。蓄水廠的功能是利用水泵將湖泊中的水抽取到所在城市的 蓄水池中。因此，只有與湖泊毗鄰的第1行的城市可以建造蓄水廠。而輸水站的功能則是通 過輸水管線利用高度落差，將湖水從高處向低處輸送。故一座城市能建造輸水站的前提，是 存在比它海拔更高且擁有公共邊的相鄰城市，已經建有水利設施。 由于第N行的城市靠近沙漠，是該國的干旱區，所以要求其中的每座城市都建有水利 設施。那么，這個要求能否滿足呢？如果能，請計算最少建造幾個蓄水廠；如果不能，求干 旱區中不可能建有水利設施的城市數目。

輸入描述 Input Description
輸入的每行中兩個數之間用一個空格隔開。 輸入的第一行是兩個正整數N和M，表示矩形的規模。 接下來N行，每行M個正整數，依次代表每座城市的海拔高度。

輸出描述 Output Description
輸出有兩行。如果能滿足要求，輸出的第一行是整數1，第二行是一個整數，代表最少 建造幾個蓄水廠；如果不能滿足要求，輸出的第一行是整數0，第二行是一個整數，代表有 幾座干旱區中的城市不可能建有水利設施。

樣例輸入 Sample Input
2 5

9 1 5 4 3

8 7 6 1 2

樣例輸出 Sample Output
1

1

數據范圍及提示 Data Size & Hint

【數據范圍】 本題共有10個測試數據，每個數據的范圍如下表所示： 測試數據編號 能否滿足要求 N M 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 對于所有的10個數據，每座城市的海拔高度都不超過10^6

2010年NOIP全國聯賽提高組

思路：我們可以從海岸的城市開始向下dfs，經過的路徑可以看做一條條線段，那么這個問題就可以抽象成線段覆蓋問題。

題解：

#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; struct cc{int l,r; }re[505][505];//記錄路徑 bool k[505];//記錄第n行干旱區的狀態 int dp[505]; int map[505][505]; bool vis[505][505]; int dx[4]={1,0,0,-1}; int dy[4]={0,1,-1,0}; int n,m; void dfs(int x,int y) {vis[x][y]=1;if(x==n)//搜到了第n行 {k[y]=1;}for(int i=0;i<4;i++){int mx=x+dx[i],my=y+dy[i];if(mx>=1&&mx<=n&&my>=1&&my<=m&&map[x][y]>map[mx][my]){if(vis[mx][my]){re[x][y].l=min(re[x][y].l,re[mx][my].l);re[x][y].r=max(re[x][y].r,re[mx][my].r);}else{dfs(mx,my);re[x][y].l=min(re[x][y].l,re[mx][my].l);re[x][y].r=max(re[x][y].r,re[mx][my].r);}}} } int main() {scanf("%d%d",&n,&m);int num=0;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){scanf("%d",&map[i][j]);}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(i==n){re[i][j].l=j,re[i][j].r=j;}else{re[i][j].l=1e7,re[i][j].r=1;}}}for(int i=1;i<=m;i++){dfs(1,i);}for(int i=1;i<=m;i++){if(k[i]==0){num++;//統計干旱區不能建水利設施的城市個數 }}if(num){printf("0\n");printf("%d",num);}else{ for(int i=1;i<=m;i++){for(int j=re[1][i].l;j<=re[1][i].r;j++){if(!dp[j]){dp[j]=dp[re[1][i].l-1]+1;}else{dp[j]=min(dp[j],dp[re[1][i].l-1]+1);}}}printf("1\n"); printf("%d",dp[m]);}return 0; }

轉載于:https://www.cnblogs.com/-feather/p/7779918.html

總結

以上是生活随笔為你收集整理的codevs 1066 引水入城（DFS+DP）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。