http://www.rqnoj.cn/problem/601
今天发现最小区间覆盖竟然是贪心，不用DP！于是我又找到这题出来撸了一发。
要找到最上面每个城市分别能覆盖最下面哪些城市，如果最下面有城市怎么都覆盖不到，就输出覆盖不到的城市数。
这样，最上面的城市能覆盖的最下面的城市一定是一个区间，不会从中间断开。因为如果断开了，那断开的这一部分怎么都没有水能流到了，可以按照覆盖不到处理。当全部能覆盖到的时候，才要用这些区间来算最小需要多少个起点城市，有覆盖不到的就不用这些区间了。居然，好像说得很复杂，就是有覆盖不到的点，记这些区间就没什么用，记错了也没关系；如果没有覆盖不到的点，这些区间就是对的。
这个部分我用q[i][j].l和q[i][j].r记录[i][j]点能达到的区间[l,r]。深搜，搜到底端节点就
q[x][y].l=min(q[x][y].l , y);
q[x][y].r=max(q[x][y].r , y);
can++;
can记录的是能到达的城市的数量，用来统计有没有城市到不了的。
因为如果(x,y)这个点能到的区间算好了之后，能到达(x,y)的点肯定包含这个区间，就不用再进入(x,y)点再算一遍区间了，直接加上这个区间就好。这样，每个点就只用进入一次。一下就能深搜完啦。
然后q[0][i].l和q[0][i].r就记录了第一行的i号节点能到的区间，接下来就是最小区间覆盖了。
以前我用的是DP，f[i]记录从(n,1)到(n,i)这个区间所需要的最少起点城市数。
f[]:=;
for i:= to m do{从[1,1]区间开始，到[1,2]区间，不断延伸，直到[1,m]区间}
begin
f[i]:=;
for j:= to m do
if (e[,j].l<=i)and(e[,j].r>=i)then
f[i]:=min(f[i],f[e[,j].l-]+);
end;
这是pascal代码，碉不碉。
然后我今天看到最小区间覆盖竟然是贪心…
每次找到包含起始节点s（这题里是0）的r最大的区间，加入结果区间里，然后s=r+1，重复直到s>=m，就覆盖完了…
AC代码：
#include<iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN 555
#define RE freopen("in.txt","r",stdin); using namespace std; const int dx[]= {,,-,};
const int dy[]= {-,,,};
const int inf=; struct Qujian
{
int l,r;
}; bool cmp(Qujian x,Qujian y)
{
return x.r>y.r;
} int n,m,can;
int a[MAXN][MAXN];
Qujian q[MAXN][MAXN];
bool w[MAXN][MAXN]; int farm();
void init(); int main()
{
//RE
while(scanf("%d%d",&n,&m)!=EOF)
{
farm();
}
return ;
} void dfs(int x,int y)
{
int i,j,nx,ny;
if(w[x][y]) return;
w[x][y]=true;
if(x==n-)
{
q[x][y].l=min(q[x][y].l , y);
q[x][y].r=max(q[x][y].r , y);
can++;
}
for(i=; i<; i++)
{
nx=x+dx[i];
ny=y+dy[i];
if(nx< || ny< || nx>=n || ny>=m) continue;
if(a[nx][ny]>=a[x][y]) continue;
if(!w[nx][ny]) dfs(nx,ny);
q[x][y].l=min(q[x][y].l , q[nx][ny].l);
q[x][y].r=max(q[x][y].r , q[nx][ny].r);
}
} int farm()
{
int i,j;
init();
for(i=; i<n; i++)
for(j=; j<m; j++)
{
scanf("%d",&a[i][j]);
}
for(i=; i<m; i++)
dfs(,i);
// for(i=0; i<n; i++)
// {
// for(j=0; j<m; j++)
// cout<<'['<<q[i][j].l<<','<<q[i][j].r<<"] ";
// cout<<endl;
// }
if(can<m)
{
printf("0\n%d\n",m-can);
}
else
{
sort(q[],q[]+m,cmp);
i=;
int ans=;
while(i<m)
{
for(j=; j<m; j++)
if(q[][j].l<=i)
{
i=q[][j].r+;
ans++;
break;
}
}
printf("1\n%d\n",ans);
} return ;
} void init()
{
int i,j;
memset(q,,sizeof(q));
can=;
for(i=; i<n; i++)
for(j=; j<m; j++)
q[i][j].l=inf;
memset(w,false,sizeof(w));
}