首页 > 代码库 > USACO 2014 JAN滑雪场建设{Gold题2}
USACO 2014 JAN滑雪场建设{Gold题2}
滑雪场建设{Gold题2}
【问题描述】
滑雪场的设计图是一个M*NM x N (1 <= M,N <= 100)的矩阵，每个格子里用一个字母R（表示粗糙）或者S（表示平整）。
比如：
RSRSSS
RSRSSS
RSRSSS
农民约翰的拖拉机每次可以将一块B*B (B <= M, B <= N)的区域全部标记B*B (B <= M, B <= N)的R或者S，他希望B能够尽量地大。一个格子可以被多次标记，下一次标记能够覆盖前一次标记，每个格子可以都至少被标记一次。
【文件输入】
第一行，两个用空格隔开的整数，分别表示M，N。
接下来2.. M+1行，每行一个M个符号，R或者S。表示用标记成的目标状态。
【文件输出】
共一行，一个整数，表示B的最大值。
【输入样例】
3 6
RSRSSS
RSRSSS
RSRSSS
【输出样例】
3
【样例说明】
首先将第1到第3列全部标记为R,然后第2到第4列全部标记为S，接下来将第3到5列全部标记为R，最后将第4到6列全部标记为S。
思路：每次考虑最后一步，能放上去的最大正方形边长是多少，然后将这块正方形上的每个点标记成任意（可R可S）以此类推下去，直到所有的点都被标记成了任意，运行结束。找最大正方形时用dp的思想来找f[i,j]:=min(min(f[i-1,j],f[i,j-1]),f[i-1,j-1])+1。可是这样的话还有最后一个点会超时，这时我们就需要使用一点点的小技巧，它叫卡时算法，略估计下大概运行几次能达到最优，然后卡时。下面上代码
1 var 2 a,f,g:array[-1..100,-1..100]of longint; //a为字母代号1表示R，2表示S，0表示任意；f,g分别表示以R和S为结尾的最大正方形 3 used:array[-1..100,-1..100]of boolean; //used表示该点是否已被处理 4 i,j,n,m,tx,ty,ans,posi,posj,flag,time,maxfg:longint; //flag记录剩余的没处理的点的个数；time用来计时 5 6 procedure openit; 7 begin 8 assign(input,‘skicourse.in‘);assign(output,‘skicourse.out‘); 9 reset(input);rewrite(output);10 end;11 12 procedure closeit;13 begin14 close(input);close(output);15 end;16 17 procedure datain; //数据读入以及处理18 var i,j:longint;19 ch:char;20 begin21 readln(n,m);22 flag:=n*m;ans:=10000000;time:=0;23 //fillchar(used,sizeof(used),false);24 //fillchar(f,sizeof(f),0);25 //fillchar(g,sizeof(g),0);26 for i:=1 to n do27 begin28 for j:=1 to m do29 begin30 read(ch);31 if ch=‘R‘ then a[i,j]:=132 else a[i,j]:=2;33 end;34 readln;35 end;36 end;37 38 function min(a,b:longint):longint;39 begin40 if a<b then min:=a41 else min:=b;42 end;43 44 function max(a,b:longint):longint;45 begin46 if a>b then max:=a47 else max:=b;48 end;49 50 51 begin52 openit;53 datain;54 while flag>0 do55 begin56 for i:=tx to n do //处理出当前最大正方形的边长57 for j:=ty to m do58 begin59 f[i,j]:=min(min(f[i-1,j],f[i,j-1]),f[i-1,j-1])+1;60 g[i,j]:=min(min(g[i-1,j],g[i,j-1]),g[i-1,j-1])+1;61 if a[i,j]=1 then g[i,j]:=0;62 if a[i,j]=2 then f[i,j]:=0;63 end;64 posi:=1;posj:=1;maxfg:=0;65 for i:=1 to n do //找出最大正方形所在的位置66 for j:=1 to m do67 if (max(f[i,j],g[i,j])>maxfg) and not used[i,j] then68 begin69 posi:=i;posj:=j;70 maxfg:=max(f[i,j],g[i,j]);71 end;72 if maxfg<ans then ans:=maxfg;73 used[posi,posj]:=true;74 for i:=posi-maxfg+1 to posi do //修改原图75 for j:=posj-maxfg+1 to posj do76 if a[i,j]<>0 then77 begin78 dec(flag);79 a[i,j]:=0;80 end;81 tx:=posi-maxfg+1;ty:=posj-maxfg+1;82 inc(time);83 if time=5000 then break; //卡时84 end;85 writeln(ans);86 closeit;87 end.
USACO 2014 JAN滑雪场建设{Gold题2}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。