首页 > 专题系列 > Java解POJ > POJ 1191 棋盘分割 [解题报告] Java
2013
11-09

POJ 1191 棋盘分割 [解题报告] Java

棋盘分割

问题描述 :

将一个8*8的棋盘进行如下分割:将原棋盘割下一块矩形棋盘并使剩下部分也是矩形,再将剩下的部分继续如此分割,这样割了(n-1)次后,连同最后剩下的矩形棋盘共有n块矩形棋盘。(每次切割都只能沿着棋盘格子的边进行)



原棋盘上每一格有一个分值,一块矩形棋盘的总分为其所含各格分值之和。现在需要把棋盘按上述规则分割成n块矩形棋盘,并使各矩形棋盘总分的均方差最小。

均方差,其中平均值,xi为第i块矩形棋盘的总分。

请编程对给出的棋盘及n,求出O’的最小值。

输入:

第1行为一个整数n(1 < n < 15)。

第2行至第9行每行为8个小于100的非负整数,表示棋盘上相应格子的分值。每行相邻两数之间用一个空格分隔。

输出:

仅一个数,为O’(四舍五入精确到小数点后三位)。

样例输入:

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

样例输出:

1.633

解题代码:

import java.util.*;  
public class Main   
{  
    static int min(int a,int b){return (a>b)? b:a;}  
    static double min(double a,double b){return (a>b)? b:a;}  
    final int Max_Int=200000000;  
    static double qr(double x){return x*x;}  
    public static void main(String[] args)  
    {  
        Scanner cin=new Scanner(System.in);  
        int a[][]=new int[10][10],s[][]=new int [10][10],sum[][][][]=new int[9][9][9][9];  
        double dp[][][][][]=new double [9][9][9][9][17];  
        int n=cin.nextInt();  
        double tot=0,ave=0;  
        for(int i=1;i<=8;i++)  
        {  
            s[i][0]=0;  
            for(int j=1;j<=8;j++)  
            {     
                a[i][j]=cin.nextInt();  
                tot+=(double)a[i][j];  
                s[i][j]=s[i][j-1]+a[i][j];  
            }  
        }  
        ave=tot/(double)n;  
        for(int i=1;i<=8;i++)  
            for(int j=i;j<=8;j++)  
                for(int k=1;k<=8;k++)  
                    for(int l=k;l<=8;l++)  
                    {  
                        sum[i][j][k][l]=0;  
                        for(int t=i;t<=j;t++)  
                            sum[i][j][k][l]+=s[t][l]-s[t][k-1];  
                        dp[i][j][k][l][1]=qr(sum[i][j][k][l]-ave);  
                    }  
        for(int v=2;v< n;v++)  
            for(int i=1;i<=8;i++)  
                for(int j=i;j<=8;j++)  
                    for(int k=1;k<=8;k++)  
                        for(int l=k;l<=8;l++)  
                        {  
                            dp[i][j][k][l][v]=100000000.0;  
                            for(int t=i;t< j;t++)  
                                dp[i][j][k][l][v]=min(dp[i][j][k][l][v],dp[i][t][k][l][v-1]+dp[t+1][j][k][l][1]);  
                            for(int t=i;t< j;t++)  
                                dp[i][j][k][l][v]=min(dp[i][j][k][l][v],dp[t+1][j][k][l][v-1]+dp[i][t][k][l][1]);  
                            for(int t=k;t< l;t++)  
                                dp[i][j][k][l][v]=min(dp[i][j][k][l][v],dp[i][j][k][t][v-1]+dp[i][j][t+1][l][1]);  
                            for(int t=k;t< l;t++)  
                                dp[i][j][k][l][v]=min(dp[i][j][k][l][v],dp[i][j][t+1][l][v-1]+dp[i][j][k][t][1]);  
                        }  
        dp[1][8][1][8][n]=100000000.0;  
        for(int t=1;t< 8;t++)  
            dp[1][8][1][8][n]=min(dp[1][8][1][8][n], dp[1][t][1][8][n-1]+dp[t+1][8][1][8][1]);  
        for(int t=1;t< 8;t++)  
            dp[1][8][1][8][n]=min(dp[1][8][1][8][n], dp[t+1][8][1][8][n-1]+dp[1][t][1][8][1]);  
        for(int t=1;t< 8;t++)  
            dp[1][8][1][8][n]=min(dp[1][8][1][8][n], dp[1][8][1][t][n-1]+dp[1][8][t+1][8][1]);  
        for(int t=1;t< 8;t++)  
            dp[1][8][1][8][n]=min(dp[1][8][1][8][n], dp[1][8][t+1][8][n-1]+dp[1][8][1][t][1]);  
        System.out.printf("%.3f", Math.sqrt(dp[1][8][1][8][n]/(double)n));  
    }  
}

  1. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮