POJ 1191 棋盤分割

棋盤分割
Time Limit: 1000MS   Memory Limit: 10000K
Total Submissions: 11013   Accepted: 3869

Description

將一個８*８的棋盤進行如下分割：將原棋盤割下一塊矩形棋盤並使剩下部分也是矩形，再將剩下的部分繼續如此分割，這樣割了(n-1)次後，連同最後剩下的矩形棋盤共有n塊矩形棋盤。(每次切割都只能沿著棋盤格子的邊進行)

原棋盤上每一格有一個分值，一塊矩形棋盤的總分為其所含各格分值之和。現在需要把棋盤按上述規則分割成n塊矩形棋盤，並使各矩形棋盤總分的均方差最小。
均方差，其中平均值，xi為第i塊矩形棋盤的總分。
請編程對給出的棋盤及n，求出O'的最小值。

Input

第1行為一個整數n(1 < n < 15)。
第2行至第9行每行為8個小於100的非負整數，表示棋盤上相應格子的分值。每行相鄰兩數之間用一個空格分隔。

Output

僅一個數，為O'（四捨五入精確到小數點後三位）。
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 3Sample Output

1.633Source

Noi 99
      我的轉移方程：
         //水平切
         dp[k][x1][y1][x2][y2]=min(dp[k][x1][y1][x2][y2],dp[1][x1][y1][t][y2]+dp[k-1][t+1][y1][x2][y2]);
         dp[k][x1][y1][x2][y2]=min(dp[k][x1][y1][x2][y2],dp[k-1][x1][y1][t][y2]+dp[1][t+1][y1][x2][y2]);
       //縱向切
        dp[k][x1][y1][x2][y2]=min(dp[k][x1][y1][x2][y2],dp[1][x1][y1][x2][t]+dp[k-1][x1][t+1][x2][y2]);
        dp[k][x1][y1][x2][y2]=min(dp[k][x1][y1][x2][y2],dp[k-1][x1][y1][x2][t]+dp[1][x1][t+1][x2][y2]);

#include <iostream>   
#include <cstdio>   
#include <cstring>   
#include <cmath>   
#define N 20   
#define INF 0x7ffffff   
#define M 8   
using namespace std;  
int sum[N][N][N][N],dp[N][N][N][N][N];  
int a[N][N];  
int main()  
{  
    //freopen("data.in","r",stdin);   
    int n;  
    while(scanf("%d",&n)!=EOF)  
    {  
        for(int i=0;i<=M-1;i++)  
        {  
            for(int j=0;j<=M-1;j++)  
            {  
                scanf("%d",&a[i][j]);  
            }  
        }  
        for(int x1=0;x1<=M-1;x1++)  
        {  
            for(int y1=0;y1<=M-1;y1++)  
            {  
                for(int x2=x1;x2<=M-1;x2++)  
                {  
                    for(int y2=y1;y2<=M-1;y2++)  
                    {  
                        if(y2==y1&&x2==x1)  
                        {  
                            sum[x1][y1][x2][y2] = a[x1][y1];  
                        }else if(x2==x1)  
                        {  
                            sum[x1][y1][x2][y2] = sum[x1][y1][x2][y2-1]+a[x2][y2];  
                        }else if(y2==y1)  
                        {  
                            sum[x1][y1][x2][y2] = sum[x1][y1][x2-1][y2] + a[x2][y2];  
                        }else  
                        {  
                            sum[x1][y1][x2][y2]=sum[x1][y1][x2][y2-1]+sum[x1][y1][x2-1][y2]-sum[x1][y1][x2-1][y2-1]+a[x2][y2];  
                        }  
                        dp[1][x1][y1][x2][y2] = sum[x1][y1][x2][y2]*sum[x1][y1][x2][y2];  
                    }  
                }  
            }  
        }  
        for(int k=2;k<=n;k++)  
        {  
            for(int x1=0;x1<=M-1;x1++)  
            {  
                for(int y1=0;y1<=M-1;y1++)  
                {  
                    for(int x2=x1;x2<=M-1;x2++)  
                    {  
                        for(int y2=y1;y2<=M-1;y2++)  
                        {  
                            dp[k][x1][y1][x2][y2]=INF;  
                            for(int t = x1;t<=x2-1;t++) //hor   
                            {  
                                dp[k][x1][y1][x2][y2]=min(dp[k][x1][y1][x2][y2],dp[1][x1][y1][t][y2]+dp[k-1][t+1][y1][x2][y2]);  
                                dp[k][x1][y1][x2][y2]=min(dp[k][x1][y1][x2][y2],dp[k-1][x1][y1][t][y2]+dp[1][t+1][y1][x2][y2]);  
                            }  
                            for(int t = y1;t<=y2-1;t++) //ver   
                            {  
                                dp[k][x1][y1][x2][y2]=min(dp[k][x1][y1][x2][y2],dp[1][x1][y1][x2][t]+dp[k-1][x1][t+1][x2][y2]);  
                                dp[k][x1][y1][x2][y2]=min(dp[k][x1][y1][x2][y2],dp[k-1][x1][y1][x2][t]+dp[1][x1][t+1][x2][y2]);  
                            }  
                        }  
                    }  
                }  
            }  
        }  
        double temp = (double)(sum[0][0][M-1][M-1])/(double)(n);  
        double res1 = temp*temp;  
        double res = (double)(dp[n][0][0][M-1][M-1])/(double)n - res1;  
        res = sqrt(res);  
        res = res*1000;  
        res+=0.5;  
        int R = (int)(res);  
        res = (double)(R)/1000;  
        printf("%.3lf\n",res);  
    }  
    return 0;  
}