Poj1191 [NOI1999]棋盘分割 — 简单的动态规划

Note: 本文最初于 2011年03月18日 星期五 16:59 在 hi.baidu.com/lydrainbowcat 发表。

一道简单的的动规，我是一次就AC的。

f[h,i,j,k,l]表示进行了h次切割后，剩余部分为第i~j行，第k~l列(包括第i,j行和第k,l列)时，切下去的部分的（各部分总和-平均值）^2的和的最小值。

另外预处理出sum[i,j]表示前i行前j列的和，m为平均值。

边界：f[1,1,8,1,8]=0.

目标：MAX { f[n,i,j,k,l]+sqr(sum[j,l]-sum[i-1,l]-sum[j,k-1]+sum[i-1,k-1]-m) }.

状态转移：最外层1~n-1循环h（切割次数），内层每次扫一遍i,j,k,l，若当前f[h,i,j,k,l]已经被赋过值，则在枚举i~j,k~l中切割那一条边，然后扩展更新f[h+1,i’,j’,k’,l’]。

Source Code

Problem: 1191		User: lydliyudong
Memory: 1584K		Time: 47MS
Language: Pascal		Result: Accepted

• Source Code

var
 f:array[0..15,0..8,0..8,0..8,0..8]of double;
 a,sum:array[0..8,0..8]of longint;
 n,h,i,j,k,l,o:longint;
 ans,m,p:double;

function min(x,y:double):double;
 begin
  if x<y then exit(x) else exit(y);
 end;

begin
 readln(n);
 for i:=1 to 8 do
  for j:=1 to 8 do
   begin
    read(a[i,j]);
    sum[i,j]:=sum[i,j-1]+sum[i-1,j]-sum[i-1,j-1]+a[i,j];
   end;
 m:=sum[8,8]/n;
 for h:=0 to n do
  for i:=1 to 8 do
   for j:=1 to 8 do
    for k:=1 to 8 do
     for l:=1 to 8 do
      f[h,i,j,k,l]:=maxlongint;
 f[1,1,8,1,8]:=0;
 for h:=1 to n-1 do
  for i:=1 to 8 do
   for j:=1 to 8 do
    for k:=1 to 8 do
     for l:=1 to 8 do
      if f[h,i,j,k,l]<>maxlongint then
       begin
        for o:=i to j do
         begin
          if o<>i then f[h+1,o,j,k,l]:=min(f[h+1,o,j,k,l],f[h,i,j,k,l]+sqr(sum[o-1,l]-sum[i-1,l]-sum[o-1,k-1]+sum[i-1,k-1]-m));
          if o<>j then f[h+1,i,o,k,l]:=min(f[h+1,i,o,k,l],f[h,i,j,k,l]+sqr(sum[j,l]-sum[o,l]-sum[j,k-1]+sum[o,k-1]-m));
         end;
        for o:=k to l do
         begin
          if o<>k then f[h+1,i,j,o,l]:=min(f[h+1,i,j,o,l],f[h,i,j,k,l]+sqr(sum[j,o-1]-sum[j,k-1]-sum[i-1,o-1]+sum[i-1,k-1]-m));
          if o<>l then f[h+1,i,j,k,o]:=min(f[h+1,i,j,k,o],f[h,i,j,k,l]+sqr(sum[j,l]-sum[j,o]-sum[i-1,l]+sum[i-1,o]-m));
         end;
       end;
 ans:=maxlongint;
 for i:=1 to 8 do
  for j:=1 to 8 do
   for k:=1 to 8 do
    for l:=1 to 8 do
     if f[n,i,j,k,l]<>maxlongint then
      begin
       p:=f[n,i,j,k,l]+sqr(sum[j,l]-sum[i-1,l]-sum[j,k-1]+sum[i-1,k-1]-m);
       if p<ans then ans:=p;
      end;
 writeln(sqrt(ans/n):0:3);
end.

šš