爱华网题目：引水入城 背景：NOIP2010 Q4 级别：NOIP 难度：3.7 算法：动态规划+搜索 数据结构：队列 很好的题，NOIP的嘛，最后一题都是很简单的实现，但是很不好想，跟双栈排序似的。 无解的情况很好写啊，BFS就过了，不要DFS会爆栈，图很大。 然后说下有解的情况，如果在上边一个点建一个蓄水场，那么它一定是可以覆盖下边一个连续的区域的（一定是连续的，如果是左边和右边都覆盖了，而中间有一个没有覆盖，那么这是无解的情况），一个左区间一个右区间，那么就可以用DP来求解f[i]表示前i个干旱区最少修建蓄水场的个数，f[i]:=min(f[l[j]-1]+1)前提是蓄水池j可以覆盖到第i格干旱区。那么求出蓄水场的左右边界就是一个问题了，暂且不说从下面每一个干旱区暴搜到上边，那是90分，说下N*M的。 既然已经知道蓄水场覆盖的是一个连续的区域的话，那么就希望他覆盖的区域最大，那么也就是希望覆盖的左边界越小越好右边界越大越好，既然是N*M的算法，那么也就是说只遍历图一边，从上向下搜，没有办法记录状态，所以还是M遍，考虑从下向上搜索，只不过是从低向高爬（不是流水了，改登山了！），从左边第一个点开始搜，那么标记他走过的路，然后他找到上边的蓄水池，因为他是第一个开始的，所以到达的那些点一定会找到这个最小最左边的点并记录为这个蓄水池所覆盖的左边界（因为左边界越小越好啊），那么接着该从第2个干旱区搜索了，碰到之前搜过的点就不继续搜索了，因为如果继续搜索的，一定回和之前的1号点所走的路是一样的，所到达的蓄水池也不会把第2个点当它的左边界（因为覆盖区间比以前变小了），所以不要走重复的路，把没走过的路走完，然后到达蓄水池，那么这次到达的蓄水池一定是之前没到达过的，记录左边界，这样左边界就找完了。那么右边界可以模仿找左边界，只不过需要从最后一行的n开始搜索，到1号点，倒着来一遍，蓄水池右边界找个最大即可。 找左右边界理论上是不能用DFS的因为有可能会爆栈，但是实际上是可以的，我是能写DFS不写BFS因为太麻烦，DFS很好写。 这样去年第四题就做完了，写起来太好写了，DNS+BFS+DP，没有各种高级数据结构和高级算法来辅助或直接求解（DP除外，因为他是一种思想），就是不好想啊，如果无法发现一个蓄水场能覆盖下面的一段区间就能至少90分，这是本题的重点。
代码：
type dui=record x,y:longint; end;const dx:array[1..4] of longint=(0,1,0,-1); dy:array[1..4] of longint=(-1,0,1,0);var a:array[0..501,0..501] of longint; ans,n,m:longint; l,r:array[0..501] of longint; b:array[0..501,0..501] of boolean; f:array[0..501] of longint; que:array[0..250010] of dui;function fmin(x,y:longint):longint;begin if x<y then exit(x) else exit(y);end;
function judge(x,y:longint):boolean;｛判断超界｝begin if x<1 thenexit(false); if x>n thenexit(false); if y<1 thenexit(false); if y>m thenexit(false); exit(true);end;
function fmax(x,y:longint):longint;begin if x>y then exit(x) else exit(y);end;
procedure bfs(sx,sy:longint);{BFS找无解情况}var x,y,i,head,tail:longint;begin if b[sx,sy]=true then exit; head:=1; tail:=1; que[1].x:=sx;que[1].y:=sy; b[sx,sy]:=true; while head<=tail do begin x:=que[head mod 250000].x; y:=que[head mod 250000].y; fori:=1 to 4 do if ( judge(x+dx[i],y+dy[i]) ) and(a[x+dx[i],y+dy[i]]<a[x,y]) and (b[x+dx
[i],y+dy[i]]=false) then begin inc(tail); //writeln(tail); que[tail mod 250000].x:=x+dx[i]; que[tail mod 250000].y:=y+dy[i]; b[x+dx[i],y+dy[i]]:=true; end; inc(head); end;
end;
procedure dfs_l(x,y,now:longint);{DFS找左边界}var i:longint;begin if b[x,y]=true then exit; b[x,y]:=true; if x=1 then l[y]:=fmin(l[y] , now); for i:=1 to 4 do if (judge(x+dx[i],y+dy[i]) ) and ( a[x+dx[i],y+dy[i]]>a[x,y]) thendfs_l(x+dx[i],y+dy[i],now);end;
procedure dfs_r(x,y,now:longint);{DFS找右边界}var i:longint;begin if b[x,y]=true then exit; b[x,y]:=true; if x=1 then r[y]:=fmax(r[y] , now); for i:=1 to 4 do if (judge(x+dx[i],y+dy[i]) ) and ( a[x+dx[i],y+dy[i]]>a[x,y]) thendfs_r(x+dx[i],y+dy[i],now);end;procedure init;var i,j:longint;begin readln(n,m); for i:=1 to n do begin forj:=1 to m do read(a[i,j]); readln; end;
ans:=0; fillchar(b,sizeof(b),false); for i:=1 to m do bfs(1,i); for i:=1 to m do if b[n,i]=false theninc(ans); if ans>0 then{无解输出} begin writeln(0); writeln(ans); close(input); close(output); halt; end; fillchar(b,sizeof(b),false); fillchar(l,sizeof(l),100); fillchar(r,sizeof(r),200); for i:=1 to m do dfs_l(n,i,i); fillchar(b,sizeof(b),false); for i:=m downto 1 do dfs_r(n,i,i);end;
procedure main;var i,j:longint;begin fillchar(f,sizeof(f),100); f[0]:=0; for i:=1 to m do{有解DP求最小建蓄水场} for j:=1 to m do if(l[j]<=i) and (r[j]>=i) then f[i]:=fmin(f[i] ,f[l[j]-1]+1);
writeln(1); writeln(f[m]);end;
begin assign(input,'in.txt'); reset(input); assign(output,'out.txt');rewrite(output); init; main; close(input); close(output);end.
