NOI 193棋盘分割.cpp

193:棋盘分割

总时间限制:: 1000ms
内存限制:: 65536kB

描述

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

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

，其中平均值

，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

来源

Noi 99

 /*

 z

 */

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 #define INF 0x3f3f3f3f

 using namespace std;

 int n;

 int s[][][][],c[][];

 int f[][][][][];

 int add(int x1,int y1,int x2,int y2 )

 {

     int w=;

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

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

           w+=c[i][j];

     return w;

 }

 int dfs(int k,int x1,int y1,int x2,int y2)

 {

     if(f[k][x1][y1][x2][y2]!=-)

        return f[k][x1][y1][x2][y2];

     f[k][x1][y1][x2][y2]=INF;

     if(x1<x2)//横切

     {

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

         {

             int t1=dfs(k-,x+,y1,x2,y2);  //取上面那么递归计算下面

             int t2=dfs(k-,x1,y1,x,y2);    //去下面那么递归计算上面

             int t=min(t1+s[x1][y1][x][y2],t2+s[x+][y1][x2][y2]);

             f[k][x1][y1][x2][y2]=min(f[k][x1][y1][x2][y2],t);

         }

     }

         if(y1<y2)

         {

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

             {

                 int t1=dfs(k-,x1,y+,x2,y2) ;   //选左边那么递归计算右边

                 int t2=dfs(k-,x1,y1,x2,y);     //选右边那么递归计算左边

                 int t=min(t1+s[x1][y1][x2][y],t2+s[x1][y+][x2][y2]);

                 f[k][x1][y1][x2][y2]=min(f[k][x1][y1][x2][y2],t);

             }

         }

     return f[k][x1][y1][x2][y2];

 }

 int main()

 {

     int x1,y1,x2,y2,n;

     scanf("%d",&n);

     memset(f,-,sizeof(f));

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

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

         scanf("%d",&c[i][j]);

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

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

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

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

           {

                int tmp=add(x1,y1,x2,y2);

                f[][x1][y1][x2][y2]=s[x1][y1][x2][y2]=tmp*tmp;

           }

     dfs(n,,,,);

     double X,ans;

     X=.*add(,,,);

     X=(X/n)*(X/n);

     //cout<<f[n][1][1][8][8]<<endl;

     ans=sqrt(1.0*f[n][][][][]/n-X);

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

     return ;

 }

#include <cstdio>

#include <iostream>

#include <cstring>

#include <cmath>

#define min(a,b) a<b?a:b

#define INF 0x3f3f3f3f

#define N 20

using namespace std;

int dp[N][][][][],s[][][][],c[][];

int add(int x1,int y1,int x2,int y2)

{

    int ans=,x,y;

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

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

            ans+=c[x][y];

        coutMMans;

    return ans;

}

int dfs(int k,int x1,int y1,int x2,int y2)

{

    if(dp[k][x1][y1][x2][y2]!=-)

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

    int x,y,t1,t2,t;

    dp[k][x1][y1][x2][y2]=INF;

    if(x2>x1)  //至少有两行才能横着切

    {

        //1.选上面：dp[k][x1][y1][x2][y2]=s[x1][y1][x][y2]+dp[k-1][x+1][y1][x2][y2];

        //2.选下面：dp[k][x1][y1][x2][y2]=s[x+1][y1][x2][y2]+dp[k-1][x1][y1][x][y2];

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

        {

            t1=dfs(k-,x+,y1,x2,y2);  //取上面那么递归计算下面

            t2=dfs(k-,x1,y1,x,y2);    //去下面那么递归计算上面

            t=min(t1+s[x1][y1][x][y2] , t2+s[x+][y1][x2][y2]);

            dp[k][x1][y1][x2][y2]=min(dp[k][x1][y1][x2][y2],t);

        }

    }

    if(y2>y1) //至少有两列才能竖着切

    {

        //1.选左边：dp[k][x1][y1][x2][y2]=s[x1][y1][x2][y]+dp[k-1][x1][y+1][x2][y2];

        //2.选右边：dp[k][x1][y1][x2][y2]=s[x1][y+1][x2][y2]+dp[k-1][x1][y1][x2][y];

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

        {

            t1=dfs(k-,x1,y+,x2,y2); //选左边那么递归计算右边

            t2=dfs(k-,x1,y1,x2,y);   //选右边那么递归计算左边

            t=min(t1+s[x1][y1][x2][y] , t2+s[x1][y+][x2][y2]);

            dp[k][x1][y1][x2][y2]=min(dp[k][x1][y1][x2][y2],t);

        }

    }

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

}

int main()

{

    int x1,x2,y1,y2,x,y,n;

    scanf("%d",&n);

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

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

            scanf("%d",&c[i][j]);

    memset(dp,-,sizeof(dp));

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

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

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

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

                {

                    int tmp=add(x1,y1,x2,y2);

                    dp[][x1][y1][x2][y2]=s[x1][y1][x2][y2]=tmp*tmp;

                }

    dfs(n,,,,);

    double X,ans;

    X=.*add(,,,);

    X=(X/n)*(X/n);

    cout<<X<<endl;

    ans=sqrt(1.0*dp[n][][][][]/n-X);

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

    return ;

}

1 1 1 1 1 1 1 3

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.矩形区域，采用Excel的方法

左上角(x1,y1):右下角(x2,y2)

2.状态：

f(i,x1,y1,x2,y2)表示

把(x1,y1):(x2,y2)分割成i块的最小segma((x-x)^2)。

对任意的矩形区域，i=1时的f值可以直接求得。

3.状态转移：f(i,x1,y1,x2,y2)

(1)枚举x1<=x<x2，横向分割成上下两个矩形

(x1,y1):(x,y2) (x+1,y1):(x2,y2)

把(x1,y1):(x,y2)分割成(i-1)矩形：f(i-1,x1,y1,x,y2)

(x+1,y1):(x2,y2)作为1个矩形: f(1,x+1,y1,x2,y2)

或者f(1,x1,y1,x,y2)+f(i-1,x+1,y1,x2,y2)

(2)同理，枚举y1<=y<y2，纵向分割成左右两个矩形

(x1,y1):(x2,y) (x1,y+1):(x2,y2)

f(i-1,x1,y1,x2,y)+f(1,x1,y+1,x2,y2)

f(1,x1,y1,x2,y)+f(i-1,x1,y+1,X2,Y2)

秒客网

NOI 193棋盘分割.cpp

193:棋盘分割

相关文章