描述
在一个遥远的国度，一侧是风景秀美的湖泊，另一侧则是漫无边际的沙漠。该国的行政区划十分特殊，刚好构成一个N行M列的矩形，其中每个格子都代表一座城市，每座城市都有一个海拔高度。
为了使居民们都尽可能饮用到清澈的湖水，现在要在某些城市建造水利设施。水利设施有两种，分别为蓄水厂和输水站。蓄水厂的功能是利用水泵将湖泊中的水抽取到所在城市的蓄水池中。因此，只有与湖泊毗邻的第1行的城市可以建造蓄水厂。而输水站的功能则是通过输水管线利用高度落差，将湖水从高处向低处输送。故一座城市能建造输水站的前提，是存在比它海拔更高且拥有公共边的相邻城市，已经建有水利设施。
由于第N行的城市靠近沙漠，是该国的干旱区，所以要求其中的每座城市都建有水利设施。那么，这个要求能否满足呢？如果能，请计算最少建造几个蓄水厂；如果不能，求干旱区中不可能建有水利设施的城市数目。
格式
输入格式
输入文件的每行中两个数之间用一个空格隔开。
输入的第一行是两个正整数N和M，表示矩形的规模。
接下来N行，每行M个正整数，依次代表每座城市的海拔高度。
输出格式
输出有两行。如果能满足要求，输出的第一行是整数1，第二行是一个整数，代表最少建造几个蓄水厂；如果不能满足要求，输出的第一行是整数0，第二行是一个整数，代表有几座干旱区中的城市不可能建有水利设施。
限制
每个测试点1s
提示
本题共有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。
题解
对于第一问，搜索判断即可。
在满足第一问的情况下，我们会发现第一行每个点所覆盖到的都是连续的一段，因为不连续的话，在第一问就会被排除了。
所以再一次搜索求出第一行每个点覆盖的区间[l,r]。之后可贪心，可动归。我用的是动归。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<algorithm>
#define mod 250000
#define ll long long
using namespace std;
int n,m,a[502][502],pd[502][502];
int xx[4]={1,-1,0,0},yy[4]={0,0,1,-1};
int qx[250002],qy[250002],f[502];
struct qujian{int l,r;} b[502];
void init()
{
scanf("%d%d",&n,&m);
int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
scanf("%d",&a[i][j]);
}
void dfs(int sy)
{
int i,t=0,w=1,nx,ny,tx,ty;
qx[0]=1; qy[0]=sy; pd[1][sy]=1;
while(t!=w)
{nx=qx[t]; ny=qy[t]; t=(t+1)%mod;
for(i=0;i<4;i++)
{tx=nx+xx[i],ty=ny+yy[i];
if(tx<1||tx>n||ty<1||ty>m) continue;
if(a[tx][ty]<a[nx][ny]&&!pd[tx][ty])
{pd[tx][ty]=1; qx[w]=tx; qy[w]=ty; w=(w+1)%mod;}
}
}
}
void findlr(int sy)
{
int i,t=0,w=1,nx,ny,tx,ty;
qx[0]=1; qy[0]=sy; b[sy].l=m+1; b[sy].r=0;
if(n==1) b[sy].l=sy, b[sy].r=sy;
memset(pd,0,sizeof(pd));
while(t!=w)
{nx=qx[t]; ny=qy[t]; t=(t+1)%mod;
for(i=0;i<4;i++)
{tx=nx+xx[i],ty=ny+yy[i];
if(tx<1||tx>n||ty<1||ty>m) continue;
if(a[tx][ty]<a[nx][ny])
{if(tx==n&&ty<b[sy].l) b[sy].l=ty;
if(tx==n&&ty>b[sy].r) b[sy].r=ty;
if(!pd[tx][ty])
{pd[tx][ty]=1; qx[w]=tx; qy[w]=ty; w=(w+1)%mod;}
}
}
}
if(b[sy].l==m+1) b[sy].l=b[sy].r=-1;
}
bool kp(const qujian &i,const qujian &j) {return i.l<j.l;}
void work()
{
int i,j,tag=1,ct=0;
for(i=1;i<=m;i++)
{if(!pd[1][i]) dfs(i);}
for(i=1;i<=m;i++)
{if(!pd[n][i])
{tag=0; ct++;}
}
if(tag==0)
{printf("0\n%d\n",ct); return ;}
for(i=1;i<=m;i++) findlr(i);
sort(b+1,b+m+1,kp);
memset(f,127,sizeof(f));
f[0]=0;
for(i=1;i<=m;i++)
{if(b[i].l==-1) continue;
for(j=b[i].l;j<=b[i].r;j++)
f[j]=min(f[j],f[b[i].l-1]+1);
}
printf("1\n%d\n",f[m]);
}
int main()
{
init(); work();
return 0;
}