分析
一开始以为这是搜索题,然而事实证明这是搜索+DP/贪心。。。
首先不难想到,蓄水厂应建在第一行比两边都高的地方。因为如果不是这种地方,那么两侧一定可以给它供水,因此加上它的答案不会减少。
那么从这些高地开始floodfill
,扩展出所有输水站可在地方,再计算出它能到达的最后一行的左右边界。
可以证得左右边界一定是连续的一段区间。因为如果存在中间分叉而导致区间不连续的情况,那么中间断掉的那些点就相当于被周围的比他低的点隔离,也就不存在其他的点可以更新它,就是无解的情况了。
那么这样我们就得到了第一行的每个点所能覆盖的区间。对应到最后一行,就成了区间覆盖问题
对于此题直接求最小覆盖数就好了。可以用贪心或DP。
代码
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#define re register
using namespace std;
int d[4][2]={{1,0},{-1,0},{0,-1},{0,1}};
bool map[510][510]; //地图访问标记
bool vis[510]; //标记数组
int m,n,g[510][510]; //输入用
int L[510],R[510]; //左右端点
int f[510]; //DP用的
struct node //线段
{
int L;
int R;
}syc[510];
bool cmp(const node a,const node b) { return a.L<b.L; } //sort用
inline void DFS(int x,int y) //floodfill
{
re int x1,y1;
for (re int i=0;i<4;i++) //4个方向
{
x1=x+d[i][0];
y1=y+d[i][1];
if (x1>n||x1<=0||y1>m||y1<=0||g[x1][y1]>=g[x][y]) continue;
if (map[x1][y1]) continue;
map[x1][y1]=true; DFS(x1,y1);
}
}
inline int read() //读入优化
{
int X=0,w=1; char ch=0;
while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();}
while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();
return X*w;
}
inline void write(int x) //输出优化
{
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
}
int main()
{
n=read(); m=read();
for (re int i=1;i<=n;i++)
for (re int j=1;j<=m;j++)
g[i][j]=read(); //输入
for (re int i=1;i<=m;i++)
{
if (g[1][i]>=g[1][i-1]&&g[1][i]>=g[1][i+1]) //比两端高的(注意要加等号,否则会orz)
{
re int l=510,r=0;
memset(map,0,sizeof(map)); //清空数组
map[1][i]=true; DFS(1,i); //标记+floodfill
for (re int j=1;j<=m;j++) //取左右边界
if (map[n][j])
{
vis[j]=true; //标记
if (!map[n][j-1]&&map[n][j]) l=j;
if (!map[n][j+1]&&map[n][j]) r=j;
}
syc[i].L=l; syc[i].R=r;
}
}
re int count=0; re bool fl=true;
for (re int i=1;i<=m;i++)
if (!vis[i]) //最后一行没有覆盖完
{
fl=false;
count++;
}
if (!fl) //不能覆盖干旱区
{
write(0); putchar('\n');
write(count); putchar('\n');
return 0;
}
else
{
memset(f,127,sizeof(f));
f[0]=0;
sort(syc+1,syc+m+1,cmp); //排序
for (re int i=1;i<=m;i++) //DP求值
for (re int j=syc[i].L;j<=syc[i].R;j++)
f[j]=min(f[syc[i].L-1]+1,f[j]);
write(1); putchar('\n');
write(f[m]); putchar('\n');
}
return 0;
}