POJ 1191棋盘分割问题

棋盘分割问题

题目大意，将一个棋盘分割成k-1个矩形，每个矩形都对应一个权值，让所有的权值最小求分法

很像区间DP，但是也不能说就是

我们只要想好了一个怎么变成两个，剩下的就好了，但是怎么变，就是变化的必要条件是什么

k——分割的个数肯定是必须的，而表示一个矩形，至少要知道两个点，所以x1,y1,x2,y2也是必须的，So,五维的DP，以前想都不敢想啊

dp[k][x1][y1][x2][y2]

先不来说他的值如何计算，先来看看如何分割

根据区间DP的思想

dp[k][x1][y1][x2][y2]

　　如果横向分割就会有一个状态 dp[k-1][x1][y1][x2][t] + dp[0][x1][t+1][x2][y2]

　　　　　　　　　　　　　　　　dp[0][x1][y1][x2][t] + dp[k-1][x1][t+1][x2][y2]

　　相对应竖向呢就会有　　　　　dp[k-1][x1][y1][t][y2] + dp[0][t+1][y1][x2][y2]

　　　　　　　　　　　　　　　　dp[0][x1][y1][t][y2] + dp[k-1][t+1][y1][x2][y2]

这就是状态转移的方程

最后就是权值的问题了

对方差公式进行化解，得到σ^2=1/n∑xi^2 - x^2

可知，要使方差最小，只需使∑xi^2最小即可，即各块分值平方和最小。平均值 x是个固定的数，跟分割的方式没有关系，

#include <iostream>

#include <cstdio>

#include <cmath>

#include <string.h>

#include <iomanip>

using namespace std;

int data[9][9];

int sum[9][9];

double dp[14][9][9][9][9];

double get_count(int x1,int y1,int x2,int y2)

{

    double ans = double(sum[x2][y2] - sum[x1-1][y2]-sum[x2][y1-1] + sum[x1-1][y1-1]);

    return ans * ans;

}

int main()

{

    int n,total = 0;

    scanf("%d",&n);

    for(int i = 1;i <= 8;i++)

    {

        for(int j = 1;j <= 8;j++)

        {

            cin>>data[i][j];

            //sum[i][j]表示棋盘(1,1)到(i,j)区域的累计分值

            sum[i][j] = sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1] + data[i][j];

            //total表示整个棋盘的分值之和

            total += data[i][j];

        }

    }

    for(int x1 = 1;x1 <= 8;x1++)

    {

        for(int y1 = 1;y1 <= 8;y1++)

        {

            for(int x2 = x1;x2 <= 8;x2++)

            {

                for(int y2 = y1;y2 <= 8;y2++)

                {

                    dp[0][x1][y1][x2][y2] = get_count(x1,y1,x2,y2);

                }

            }

        }

    }

    for(int k = 1;k < n;k++)

    {

        for(int x1 = 1;x1 <= 8;x1++)

        {

            for(int y1 = 1;y1 <= 8;y1++)

            {

                for(int x2 = x1;x2 <= 8;x2++)

                {

                    for(int y2 = y1;y2 <= 8;y2++)

                    {

                        int t;

                        dp[k][x1][y1][x2][y2] = (double)(1 << 30);

                        for(t = x1;t < x2;t++)

                        {

                            dp[k][x1][y1][x2][y2] = min(dp[k][x1][y1][x2][y2],dp[0][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[0][t+1][y1][x2][y2]);

                        }

                        for(t = y1;t < y2;t++)

                        {

                            dp[k][x1][y1][x2][y2] = min(dp[k][x1][y1][x2][y2],dp[0][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[0][x1][t+1][x2][y2]);

                        }

                    }

                }

            }

        }

    }

    double ans = dp[n-1][1][1][8][8] * 1.0 / n - ((double)total*1.0/n)*((double)total*1.0/n);

    //printf("%d    %.3lf\n",total,dp[n-1][1][1][8][8]);

    printf("%.3lf\n",sqrt(ans));

    return 0;

}

巴特西

POJ 1191棋盘分割问题

最新文章

热门文章