PKU 1191盤分割再帰解法

【題意の簡単な説明】
8*8の碁盤があり、現在の碁盤を毎回半分に分けて、半分を選んで得点を続けます.
全部でn-1回に分けます.
このn個の碁盤の最小平均分散はいくらですか?
    (n<15)
 
 
【分析】
まず数式を変形します.
         ans^2  =  ∑xi^2/n - (x)^2
明らかに、ブロック数は一定のnであるため、平均数(x)はすべての数字の和に等しく、nを除く.
では、各ブロックの最小二乗和だけを必要とします.これは典型的なDPです.
     F[k,r1,c1,r2,c2] 
     =  Min{  F[k-1,r1,c1,i,c2] + W[i+1,c1,r2,c2],
              F[k-1,i+1,c1,r2,c2] + W[r1,c1,i,c2],
              F[k-1,r1,c1,r2,i] + W[r1,i+1,r2,c2],
              F[k-1,r1,i+1,r2,c2] + W[r1,c1,r2,i] } 
W[a,b,c,d]=S[a,b,c,d]^2
ここでS[a,b,c,d]は矩形(a,b,c,d)の数字と
     S[a,b,c,d]=sum[c,d]-sum[c,b-1]-sum[a-1,d]+sum[a-1,b-1]
     sum[a,b] = sum[a-1,b] + sum[a,b-1] - sum[a-1,b-1]
Time Limit: 1000MS
 
Memory Limit: 10000K
Total Submissions: 4834
 
Accepted: 1738
Description
1つの8*8の碁盤を次のように分割する:元の碁盤を矩形の碁盤に切り取り、残りの部分も矩形にし、残りの部分をこのように分割し続け、(n-1)回切った後、最後に残った矩形の碁盤とともにn個の矩形の碁盤を共有する.(カットは毎回碁盤の格子の縁に沿ってしかできません)
元の碁盤には各格に1つのスコアがあり、1つの矩形の碁盤の総スコアはその含まれる各格のスコアの和である.ここで,碁盤を上記規則に従ってn個の矩形碁盤に分割し,各矩形碁盤の総得点の平均分散を最小にする必要がある.
平均分散、平均値、x
iは、i番目の矩形碁盤の総得点である.
与えられた碁盤およびnをプログラミングしてO'の最小値を求めてください.
Input
第1の動作は整数n(12行目から9行目までの行ごとに100未満の非負の整数が8個あり、碁盤上の対応する格子のスコアを表す.行ごとに隣接する2つの数の間にスペースで区切られます.
Output
1つの数だけ、O'(小数点以下3桁まで四捨五入).
Sample Input

3
1 1 1 1 1 1 1 3
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0
1 1 1 1 1 1 0 3

Sample Output

1.633

Source
Noi 99
#include
#include
int n,sum[10][10]={0};
double ans;
double f[15][9][9][9][9]={0};
int    flag[15][9][9][9][9]={0};
double  w(int a,int b,int c,int d)
{
      return sum[c][d]-sum[c][b-1]-sum[a-1][d]+sum[a-1][b-1];
}
double dp(long k,long r1,long c1,long r2,long c2)
{
       double tmp=99999999;
       int   i;
       double   kk;
       if(k==1)
        return w(r1,c1,r2,c2)*w(r1,c1,r2,c2);
       if(r1>r2) return 9999999;
       if(c1>c2) return 9999999;
       if(flag[k][r1][c1][r2][c2])
        return f[k][r1][c1][r2][c2];
       for(i=r1;i<=r2;i++)
       {
         kk=dp(k-1,r1,c1,i,c2)+w(i+1,c1,r2,c2)*w(i+1,c1,r2,c2);
         if(kk          tmp=kk;
         kk=dp(k-1,i+1,c1,r2,c2)+w(r1,c1,i,c2)*w(r1,c1,i,c2);
         if(kk          tmp=kk;
       }
       for(i=c1;i<=c2;i++)
       {
         kk=dp(k-1,r1,c1,r2,i)+w(r1,i+1,r2,c2)*w(r1,i+1,r2,c2);
         if(kk          tmp=kk;
         kk=dp(k-1,r1,i+1,r2,c2)+w(r1,c1,r2,i)*w(r1,c1,r2,i);
         if(kk          tmp=kk;
       }
       f[k][r1][c1][r2][c2]=tmp;
       flag[k][r1][c1][r2][c2]=1;
       return tmp;
}
int main()
{
 freopen("in.txt","r",stdin);
 freopen("out.txt","w",stdout);
     int  x,i,j;
     scanf("%d",&n);
     for(i=1;i<=8;i++)
      for(j=1;j<=8;j++)
      {
       scanf("%d",&x);
       sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+x;
      }
     ans=(-1)*(1.0*sum[8][8]/n)*(1.0*sum[8][8]/n);
     printf("%.3lf/n",sqrt(dp(n,1,1,8,8)/n+ans));
    return 0;
}