三只小猪盖房子 盖房子_分析

三只小猪盖房子盖房子_分析:这道题是一道题动态规划的经典题目，我们应该记住这个模型，我们设f[I,j]为以(I,j)为右下角的最大正方形的长度。那么这样进行转移f[I,j]=min{f[i-1,j],f[I,j-1],f[i-1,j-1]}，有些人可能会问为什么是min,接下来我就解释:************************************************************我们设f[i-1,j]=3，首先我们可以保证红色区域为1,再设1f[I,j-1]=2那么绿色区域为1************************************************************我们设f[i-1,j-1]=3，那么蓝色区域为1.************************************************************很明显，我们应该选取最小值，才可以确定以(I,j)为右下角的最大正方形长度2程序:{vijos1057盖房子dtghByLymfsAccepted0MS}ProgramEx;ConstInfile=„vijos1057.in?;Outfile=„vijos1057.out?;3Varf:Array[1..1000,1..1000]OfLongint;x,n,m,i,j,ans:longint;FunctionMin(A,b:Longint):Longint;beginIfAEnd;BeginAssign(Input,Infile);Reset(input);Assign(Output,Outfile);Rewrite(Output);Readln(m,n);Read(x);4ans:=0;Ifx=1ThenF[1,1]:=1ElseF[1,1]:=0;Iff[1,1]>ansThenANs:=F[1,1];Forj:=2TonDobegin{注意边界处理}Read(x);Ifx=1ThenF[1,j]:=1ElseF[1,j]:=0;IfF[1,j]>ansThenAns:=F[1,j];End;Readln;Fori:=2TomDoBeginRead(x);Ifx=1ThenF[i,1]:=1ElseF[i,1]:=0;IfF[i,1]>AnsThenAns:=F[i,1];5Forj:=2TonDoBeginRead(x);Ifx=1T盖房子_分析henBeginF[i,j]:=Min(F[i-1,j],F[i-1,j-1]);F[i,j]:=Min(F[i,j],F[i,j-1]);F[i,j]:=F[i,j]+1;IfF[i,j]>AnsThenAns:=F[i,j];EndElseBeginF[i,j]:=0;End;End;Readln;6End;Writeln(ans);Close(Input);Close(Output);End.百度搜索“就爱阅读”,专业资料,生活学习,尽在就爱阅读网92to.com,您的在线图馆7