【NOIP2010】引水入城

终于自己想出来一道题，感动非常 原题： 在一个遥远的国度，一侧是风景秀美的湖泊，另一侧则是漫无边际的沙漠。该国的行政区划十分特殊，刚好构成一个N 行M 列的矩形，如上图所示，其中每个格子都代表一座城市，每座城市都有一个海拔高度。 （图略 为了使居民们都尽可能饮用到清澈的湖水，现在要在某些城市建造水利设施。水利设施有两种，分别为蓄水厂和输水站。蓄水厂的功能是利用水泵将湖泊中的水抽取到所在城市的蓄水池中。 因此，只有与湖泊毗邻的第1 行的城市可以建造蓄水厂。而输水站的功能则是通过输水管线利用高度落差，将湖水从高处向低处输送。故一座城市能建造输水站的前提，是存在比它海拔更高且拥有公共边的相邻城市，已经建有水利设施。由于第N 行的城市靠近沙漠，是该国的干旱区，所以要求其中的每座城市都建有水利设施。那么，这个要求能否满足呢？如果能，请计算最少建造几个蓄水厂；如果不能，求干旱区中不可能建有水利设施的城市数目。 n,m<=500 虽然说是自己想出来的，但是感觉还是受到以前做过一遍以及题目tag的影响 首先我们已经知道这题是搜索，那么就考虑搜索策略 首先需要注意到的一个非常关键的点是题目要求的是蓄水塔最少而不是水利设施最少！ 一开始我看成水利设施，这样感觉就很难了 既然求蓄水塔最少的话，首先可以先把河边种满蓄水塔，这样判断是否有解的同时还能统计不可能建有水利设施的城市数 其实开始不判断也可以，放到后面判断也不是很麻烦 然后就判断最少需要种多少个蓄水塔 不妨看看给河边的某个格子种上塔，这个塔能覆盖的范围是多少 容易猜测一个塔能覆盖的范围一定是一个区间，可以很容易地用反证法证明 假设某个塔的覆盖范围不是一段连续的区间，因为我们不用考虑中间的水利设施的数量，所以中间不能被覆盖到的格子（包括最底下的和中间的）周围一定被其他的水利设施包起来了 这样就说明任何一个格子都不能覆盖到这些格子，因为如果有格子能覆盖到，我们不用考虑水利设施的数量，完全可以把这些格子也覆盖上 那么这些不能被覆盖的格子（这里指最底层的）其他的塔也覆盖不上，就无解了 （好吧开始判断无解还是挺有用的 确定一个塔覆盖的是一个区间之后，就是区间覆盖问题了，数据量很小，bfs出每个塔对应的区间，然后随便dp一下即可 1A的那一刻感觉花都开了~ 诶，只能继续努力了~  代码： ```cpp #include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; int rd(){int z=0,mk=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')mk=-1; ch=getchar();} while(ch>='0'&&ch<='9'){z=(z<<3)+(z<<1)+ch-'0'; ch=getchar();} return z*mk; } struct nds{int l,r;}b[510]; int fx[4]={1,-1,0,0},fy[4]={0,0,1,-1}; int n,m,a[510][510]; bool vstd[510][510]; int q[310000],hd=0; int f[510]; bool chck(int x,int y,int z){ return x+fx[z]>=1 && x+fx[z]<=n && y+fy[z]>=1 && y+fy[z]<=m;} void bfs(){//因为后面的搜索是完全一样的bfs，写成函数方便得多 for(int k=1;k<=hd;++k){ int x=q[k]/m+1,y=q[k]%m+1; for(int i=0;i<4;++i)if(!vstd[x+fx[i]][y+fy[i]] && chck(x,y,i)) if(a[x][y]>a[x+fx[i]][y+fy[i]]) vstd[x+fx[i]][y+fy[i]]=true,q[++hd]=(x+fx[i]-1)*m+y+fy[i]-1; //cout<<x<<" "<<y<<endl; } } bool cmp(nds x,nds y){ return x.l==y.l ? x.r<y.r : x.l<y.l;} int main(){//freopen("ddd.in","r",stdin); memset(vstd,0,sizeof(vstd)); cin>>n>>m; for(int i=1;i<=n;++i)for(int j=1;j<=m;++j) a[i][j]=rd(); for(int i=1;i<=m;++i) q[++hd]=i-1,vstd[1][i]=true; bfs(); int mk=0; for(int i=1;i<=m;++i)if(!vstd[n][i]) ++mk; if(mk){ cout<<0<<endl<<mk<<endl; return 0;} for(int t=1;t<=m;++t){ memset(vstd,0,sizeof(vstd));//注意每次对bfs进行配置 q[hd=1]=t-1,vstd[1][t]=true; bfs(); for(int i=1;i<=m;++i){ if(vstd[n][i] && !vstd[n][i-1]) b[t].l=i; if(vstd[n][i] && !vstd[n][i+1]) b[t].r=i; } } sort(b+1,b+m+1,cmp); memset(f,10,sizeof(f)); f[0]=0; for(int i=1;i<=m;++i) for(int j=b[i].l;j<=b[i].r;++j) f[j]=min(f[j],f[b[i].l-1]+1); cout<<1<<endl<<f[m]<<endl; return 0; } ```