今天发现最小区间覆盖竟然是贪心，不用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[0]:=0; for i:=1 to m do{ 从[1,1]区间开始，到[1,2]区间，不断延伸，直到[1,m]区间} begin f[i]:=501; for j:=1 to m do if (e[1,j].l<=i)and(e[1,j].r>=i)then f[i]:=min(f[i],f[e[1,j].l-1]+1); end; 这是pascal代码，碉不碉。
然后我今天看到最小区间覆盖竟然是贪心…
每次找到包含起始节点s（这题里是0）的r最大的区间，加入结果区间里，然后s=r+1，重复直到s>=m，就覆盖完了…
AC代码：
1 #include2 #include 3 #include 4 #include 5 #include 6 #define MAXN 555 7 #define RE freopen("in.txt","r",stdin); 8 9 using namespace std; 10 11 const int dx[4]= { 0,0,-1,1}; 12 const int dy[4]= {-1,1,0,0}; 13 const int inf=9999; 14 15 struct Qujian 16 { 17 int l,r; 18 }; 19 20 bool cmp(Qujian x,Qujian y) 21 { 22 return x.r>y.r; 23 } 24 25 int n,m,can; 26 int a[MAXN][MAXN]; 27 Qujian q[MAXN][MAXN]; 28 bool w[MAXN][MAXN]; 29 30 int farm(); 31 void init(); 32 33 int main() 34 { 35 //RE 36 while(scanf("%d%d",&n,&m)!=EOF) 37 { 38 farm(); 39 } 40 return 0; 41 } 42 43 void dfs(int x,int y) 44 { 45 int i,j,nx,ny; 46 if(w[x][y]) return; 47 w[x][y]=true; 48 if(x==n-1) 49 { 50 q[x][y].l=min(q[x][y].l , y); 51 q[x][y].r=max(q[x][y].r , y); 52 can++; 53 } 54 for(i=0; i<4; i++) 55 { 56 nx=x+dx[i]; 57 ny=y+dy[i]; 58 if(nx<0 || ny<0 || nx>=n || ny>=m) continue; 59 if(a[nx][ny]>=a[x][y]) continue; 60 if(!w[nx][ny]) dfs(nx,ny); 61 q[x][y].l=min(q[x][y].l , q[nx][ny].l); 62 q[x][y].r=max(q[x][y].r , q[nx][ny].r); 63 } 64 } 65 66 int farm() 67 { 68 int i,j; 69 init(); 70 for(i=0; i