題目描述

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

為了使居民們都盡可能飲用到清澈的湖水，現在要在某些城市建造水利設施。水利設施有兩種，分別為蓄水廠和輸水站。蓄水廠的功能是利用水泵將湖泊中的水抽取到所在城市的蓄水池中。

因此，只有與湖泊毗鄰的第1 行的城市可以建造蓄水廠。而輸水站的功能則是通過輸水管線利用高度落差，將湖水從高處向低處輸送。故一座城市能建造輸水站的前提，是存在比它海拔更高且擁有公共邊的相鄰城市，已經建有水利設施。由于第N 行的城市靠近沙漠，是該國的干旱區，所以要求其中的每座城市都建有水利設施。那么，這個要求能否滿足呢？如果能，請計算最少建造幾個蓄水廠；如果不能，求干旱區中不可能建有水利設施的城市數目。

輸入輸出格式

輸入格式：

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

輸出格式：

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

輸入輸出樣例

輸入樣例#1：
【輸入樣例1】 2 5 9 1 5 4 3 8 7 6 1 2【輸入樣例2】 3 6 8 4 5 6 4 4 7 3 4 3 3 3 3 2 2 1 1 2 輸出樣例#1：
【輸出樣例1】 1 1【輸出樣例2】 1 3
看了幾個題解，搜索判斷是否能覆蓋所有干旱區域，貪心+動態規劃找出最少需要幾個抽水站。犯了一個很嚴重的審題錯誤，誤把所有的城市視作干旱區域。想了一個很low的貪心，將第一行從高到低開始深搜建立抽水站，到全覆蓋需要幾個抽水站，貪了40分。
炒了個題解http://blog.csdn.net/loi__dijiang/article/details/49000357，發現他只能得90分。又通過看題解發現搜索一次的通病就是第六個點不過，于是又修改了先搜索一次，回答第一問，再搜索一次，回答第二問。可能是因為這個點正好是個找不到的店，提前rentun了，題目中如果城市的連通度大，時間復雜度到500*500*500，就超時拉。
參考代碼：
#include<iostream> #include<algorithm> #include<cstring>using namespace std; struct factory{int l,r; }p[501];int n,m,map[501][501],f[501],cnt=0,cun=0; int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};bool vis[501][501]={0},ans[501]={0};/* bool comp(const factory &a,const factory &b) {return a.l<b.l; } */ void dfs(int x,int y,int ori) { if(x==m&&vis[m][y]==0) cun++;vis[x][y]=1;if(cun==n)return;if(x==m){ans[y]=1;p[ori].l=min(p[ori].l,y);p[ori].r=max(p[ori].r,y);}for(int i=0;i<4;i++){int dx=x+dir[i][0],dy=y+dir[i][1];if(dx<1||dx>m||dy<1||dy>n)continue;if(map[dx][dy]<map[x][y]&&!vis[dx][dy])dfs(dx,dy,ori);}}int main() {cin>>m>>n;for(int i=1;i<=n;++i)p[i].l=f[i]=300000;f[0]=0;for(int i=1;i<=m;++i)for(int j=1;j<=n;++j)cin>>map[i][j];for(int i=1;i<=n;++i){if(vis[1][i]==0)dfs(1,i,i);//memset(vis,0,sizeof(vis));}if(cun<n){if(cnt)cout<<0<<endl<<n-cun;return 0;}for(int i=1;i<=n;++i){memset(vis,0,sizeof(vis));cun=0;dfs(1,i,i);} for(int i=1;i<=n;++i)for(int j=1;j<=n;++j){if(i>=p[j].l&&i<=p[j].r)f[i]=min(f[i],f[p[j].l-1]+1);} cout<<1<<endl<<f[n]; return 0;}

總結

以上是生活随笔為你收集整理的noip2010引水入城-搜索+贪心的全部內容，希望文章能夠幫你解決所遇到的問題。

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