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;  
}

补充：软件开发 , C++ ,