棋盘分割

终于过了。

题目：http://poj.org/problem?id=1191

dp，水平有限，想不清更新顺序，所以打的记忆化,

f[n,x,y,xx,yy]表示还剩下n块，以及还剩下的这部分的左上角右下角坐标，所存储的最优值

需要对公式变形为n*σ*σ=Σ（xi-x )^2，维护的即为各项的和

代码：

program sky;
constmaxn = 10000000;
vari,j,n,x:longint;ave:extended;a:array[0..8,0..8] of longint;f:array[0..16,0..9,0..9,0..9,0..9] of extended;
function min(qq,ww:extended):extended;
beginif qq>ww then exit(ww); exit(qq);
end;
function get(x,y,xx,yy:longint):extended;
vartp:longint;
begintp:=a[xx,yy]-a[x-1,yy]-a[xx,y-1]+a[x-1,y-1];get:=sqr(tp-ave);
end;
function dp(n,x,y,xx,yy:longint):extended;
vari:longint;
beginif f[n,x,y,xx,yy]<>0 then exit(f[n,x,y,xx,yy]);if n=1 thenbeginf[n,x,y,xx,yy]:=get(x,y,xx,yy);exit(f[n,x,y,xx,yy]);end;f[n,x,y,xx,yy]:=maxn;for i:=x to xx-1 do{题目的限制只用递归一边，另一边不再切割}begin{一开始加了一些限制条件，比如(i-x+1>=n)才搜，后来发现不对}{因为加上会丢状态，有可能横着切不了竖着可以切}f[n,x,y,xx,yy]:=min(f[n,x,y,xx,yy],dp(n-1,x,y,i,yy)+dp(1,i+1,y,xx,yy));f[n,x,y,xx,yy]:=min(f[n,x,y,xx,yy],dp(1,x,y,i,yy)+dp(n-1,i+1,y,xx,yy));end;for i:=y to yy-1 dobeginf[n,x,y,xx,yy]:=min(f[n,x,y,xx,yy],dp(n-1,x,y,xx,i)+dp(1,x,i+1,xx,yy));f[n,x,y,xx,yy]:=min(f[n,x,y,xx,yy],dp(1,x,y,xx,i)+dp(n-1,x,i+1,xx,yy));end;exit(f[n,x,y,xx,yy]);
end;
beginassign(input,'fgqp.in'); reset(input);assign(output,'fgqp.out'); rewrite(output);readln(n);for i:=1 to 8 dofor j:=1 to 8 dobeginread(x);a[i,j]:=a[i-1,j]+a[i,j-1]-a[i-1,j-1]+x;end;ave:=a[8,8]/n;writeln(sqrt(dp(n,1,1,8,8)/n):0:3);close(input); close(output);
end.

转载于:https://www.cnblogs.com/skysun/archive/2012/05/24/2516286.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！