noip2010引水入城

贪心 DFS

这道题fst了

题面

戳我

解析

我一开始的想法是，按照高度给第一行排序，然后贪心地选取目前到不了的，高度最高的第一行的点来$DFS$，一旦满足题目要求就退出。
但是这样有问题，只有$40pts$。
因为高度越高，不一定代表能走的越远。

有一个在考场上不一定能想到的结论：当可以满足所有位置的时候，在每个位置建立蓄水场，那么它影响的范围一定是一段连续区间。
这个证还是很好证：如果中间被隔开了，那么中间那个点就不可能被影响了，因为它所在的不被影响的块被可以被影响的部分完全包围，这都影响不到就没办法了。

然后问题转化为覆盖整段区间所需要的线段数。
在判定可行后，把所有区间按左端点排序，贪心地选取即可。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#define ll long long
#define re register
#define il inline
#define fp(i,a,b) for(re int i=a;i<=b;++i)
#define fq(i,a,b) for(re int i=a;i>=b;--i)
using namespace std;
const int N=600;
int n,m,w[N][N],ans,mx[4]={1,-1,0,0},my[4]={0,0,1,-1},tot;
bool vis[N][N],ok[N];
struct dat{int l,r;il bool operator < (const dat &o) const {return l<o.l;}}a[N];
il ll gi()
{
  re ll x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
il void DFS(re int x,re int y)
{
  vis[x][y]=1;
  fp(i,0,3)
    {
      re int xx=x+mx[i],yy=y+my[i];
      if(xx<1||xx>n||yy<1||yy>m||vis[xx][yy]||w[xx][yy]>=w[x][y]) continue;
      DFS(xx,yy);
    }
}
int main()
{
  n=gi();m=gi();
  fp(i,1,n)
      fp(j,1,m) w[i][j]=gi();
  fp(i,1,m)
    {
      DFS(1,i);
      fp(j,1,m)
    {
      if(!vis[n][j-1]&&vis[n][j]) a[i].l=j;
      if(vis[n][j]&&!vis[n][j+1]) a[i].r=j;
      ok[j]|=vis[n][j];
    }
      memset(vis,0,sizeof(vis));
    }
  fp(i,1,m) if(!ok[i]) ++tot;
  if(tot) return printf("0\n%d\n",tot),0;
  sort(a+1,a+1+m);
  re int mxr=0,i=1;
  while(!a[i].l&&i<=m) ++i;
  for(re int j=i;i<=m&&mxr<m;i=j)
    {
      re int now=mxr;
      while(a[j].l<=mxr+1&&j<=m) now=max(now,a[j++].r);
      ++ans;mxr=now;
    }
  printf("1\n%d\n",ans);
  return 0;
}