题目描述
在一个遥远的国度，一侧是风景秀美的湖泊，另一侧则是漫无边际的沙漠。该国的行政区划十分特殊，刚好构成一个N 行M 列的矩形，如上图所示，其中每个格子都代表一座城市，每座城市都有一个海拔高度。
为了使居民们都尽可能饮用到清澈的湖水，现在要在某些城市建造水利设施。水利设施有两种，分别为蓄水厂和输水站。蓄水厂的功能是利用水泵将湖泊中的水抽取到所在城市的蓄水池中。
因此，只有与湖泊毗邻的第1 行的城市可以建造蓄水厂。而输水站的功能则是通过输水管线利用高度落差，将湖水从高处向低处输送。故一座城市能建造输水站的前提，是存在比它海拔更高且拥有公共边的相邻城市，已经建有水利设施。由于第N 行的城市靠近沙漠，是该国的干旱区，所以要求其中的每座城市都建有水利设施。那么，这个要求能否满足呢？如果能，请计算最少建造几个蓄水厂；如果不能，求干旱区中不可能建有水利设施的城市数目。
解题报告:
数据范围小，可以乱来:
首先明确，如果所有所有的干旱区都能建造，那么对于第一行如果建造一个蓄水场，一定覆盖的区域是一个区间，那么我们做(m)遍bfs，求出第一行所有点能覆盖的区间，然后就可以转化为线段覆盖问题，即用最少的线段覆盖所有的位置，如果两线段有交 (f[i]=Min(f[i],f[j]+1)) 注意这样做完只有90分，首先(m)遍bfs就是(O(n^3)),需要优化，首先如果前一个位置的海拔大于他，那么就可以不用bfs了，因为前一个点覆盖的区域一定比他大，所以可以忽略，然后对于bfs我们可以不(O(n^2))清空vis数组，用一个栈来存走过的节点即可，做到这就可以AC了
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define RG register
#define il inline
#define iter iterator
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
const int N=505;
int a[N][N],n,m;bool vis[N][N];
struct Que{
int x,y;
}q[N*N*2];
int mx[4]={0,0,1,-1},my[4]={1,-1,0,0};
bool tar[N];
struct node{
int l,r;
bool operator <(const node &p)const{
return r<p.r;
}
}e[N];
int num=0,f[N],st[N*N][2],top=0;
void bfs(int sta){
int t=0,sum=1,x,y,tx,ty,l=N,r=0;
q[sum].x=1;q[sum].y=sta;vis[1][sta]=true;
while(t!=sum){
x=q[++t].x;y=q[t].y;st[++top][0]=x;st[top][1]=y;
if(x==n){
tar[y]=true;l=Min(l,y);r=Max(r,y);
}
for(int i=0;i<4;i++){
tx=x+mx[i];ty=y+my[i];
if(!a[tx][ty] || vis[tx][ty] || a[x][y]<=a[tx][ty])continue;
q[++sum].x=tx;q[sum].y=ty;vis[tx][ty]=true;
}
}
if(r)e[++num].l=l,e[num].r=r;
while(top)vis[st[top][0]][st[top][1]]=false,top--;
}
void work()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&a[i][j]);
for(int i=1;i<=m;i++)if(a[1][i-1]<=a[1][i])bfs(i);
int tot=0;
for(int i=1;i<=m;i++)tot+=tar[i];
if(tot<m){printf("0
%d
",m-tot);return ;}
sort(e+1,e+num+1);
for(int i=1;i<=num;i++){
if(e[i].l==1)f[i]=1;
else f[i]=N;
}
for(int i=1;i<=num;i++){
for(int j=i-1;j>=1;j--){
if(e[j].r<e[i].l-1)break;
f[i]=Min(f[i],f[j]+1);
}
}
int ans=N;
for(int i=num;i>=1 && e[i].r==m;i--)
ans=Min(ans,f[i]);
printf("1
%d
",ans);
}
int main()
{
freopen("flow.in","r",stdin);
freopen("flow.out","w",stdout);
work();
return 0;
}