3208: 花神的秒题计划Ⅰ
Time Limit: 16 Sec Memory Limit: 128 MBSubmit: 691 Solved: 471[][][]Description
背景【backboard】：
Memphis等一群蒟蒻出题中，花神凑过来秒题……
描述【discribe】：
花花山峰峦起伏，峰顶常年被雪，Memphis打算帮花花山风景区的人员开发一个滑雪项目。
我们可以把风景区看作一个n*n的地图，每个点有它的初始高度，滑雪只能从高处往低处滑【严格大于】。但是由于地势经常变动【比如雪崩、滑坡】，高度经常变化；同时，政府政策规定对于每个区域都要间歇地进行保护，防止环境破坏。现在，滑雪项目的要求是给出每个n*n个点的初始高度，并给出m个命令，C a b c表示坐标为a,b的点的高度改为c；S a b c d表示左上角为a,b右下角为c,d的矩形地区开始进行保护，即不能继续滑雪；B a b c d表示左上角为a b,右下角为c d的矩形地区取消保护，即可以开始滑雪；Q表示询问现在该风景区可以滑雪的最长路径为多少。对于每个Q要作一次回答。
花神一看，这不是超简单！立刻秒出了标算~
Input
第一行n，第二行开始n*n的地图，意义如上；接下来一个m，然后是m个命令，如上
Output
对于每一个Q输出单独一行的回答
Sample Input
5 1 2 3 4 5 10 9 8 7 6 11 12 13 14 15 20 19 18 17 16 21 22 23 24 25 5 C 1 1 3 Q S 1 3 5 5 S 3 1 5 5 Q
Sample Output
24 3 样例解释： 第一个Q路线为：25->24->23->22….->3->2 第二个Q的路线为：10->9->2
HINT
100%的数据：1<=n<=700;1<=m<=1000000;其中Q、S、B操作总和<=100;
题中所有数据不超过2*10^9 题解
记忆化搜索……太裸了……DP也行
1 /************************************************************** 2 Problem: 3208 3 User: 1090900715 4 Language: Pascal 5 Result: Accepted 6 Time:16576 ms 7 Memory:4544 kb 8 ****************************************************************/ 9 10 program j01;11 var f,h:array[0..700,0..700]of longint;12 bo:array[0..700,0..700]of boolean;13 c:array[0..4,0..1]of longint;14 n,m,i,j,a,b,c1,d,ans:longint;15 ch:char;16 17 function max(a,b:Longint):longint;18 begin19 if a>b then exit(a) else exit(b);20 end;21 22 function jud(x,y,x1,y1:longint):boolean;23 begin24 if (x1<=0)or(x1>n) then exit(false);25 if (y1<=0)or(y1>n) then exit(false);26 exit((h[x,y]>h[x1,y1])and bo[x1,y1]);27 end;28 29 procedure dfs(i,j:longint);30 var x:longint;31 begin32 if f[i,j]<>0 then exit;33 f[i,j]:=1;34 for x:=1 to 4 do35 if jud(i,j,i+c[x,0],j+c[x,1]) then36 begin37 dfs(i+c[x,0],j+c[x,1]);38 f[i,j]:=max(f[i,j],f[i+c[x,0],j+c[x,1]]+1);39 end;40 ans:=max(ans,f[i,j]);41 end;42 43 begin44 readln(n);45 for i:=1 to n do46 for j:=1 to n do47 read(h[i,j]);48 fillchar(bo,sizeof(bo),1);49 c[1,0]:=0;c[1,1]:=1;50 c[2,0]:=0;c[2,1]:=-1;51 c[3,0]:=-1;c[3,1]:=0;52 c[4,0]:=1;c[4,1]:=0;53 readln(m);54 while m>0 do55 begin56 dec(m);57 read(ch);58 while not(ch in['C','S','B','Q']) do read(ch);59 if ch='C' then60 begin61 readln(a,b,c1);62 h[a,b]:=c1;63 end;64 if ch='S' then65 begin66 readln(a,b,c1,d);67 for i:=a to c1 do68 for j:=b to d do69 bo[i,j]:=false;70 end;71 if ch='B' then72 begin73 readln(a,b,c1,d);74 for i:=a to c1 do75 for j:=b to d do76 bo[i,j]:=true;77 end;78 if ch='Q' then79 begin80 fillchar(f,sizeof(f),0);81 ans:=0;82 for i:=1 to n do83 for j:=1 to n do84 if (f[i,j]=0)and(bo[i,j]) then dfs(i,j);85 writeln(ans);86 end;87 end;88 end.