poj 1191 棋盘分割（dp）-白红宇

poj 1191 棋盘分割（dp）

阅读量：5333 次

发布时间：2019-06-15

本文共 3269 字，大约阅读时间需要 10 分钟。

好纠结的一道题啊，一开始写错了个字母，跳了半天，后来脚上去竟然不对，，看了 discuss 里面的将所有数据改为 double 类型秒过，汗。。。。。。。。。

棋盘分割

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 9151		Accepted: 3215

Description

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

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

均方差

$\sigma=\sqrt{\frac{\sum_{i=1}^n(x_i-\bar{x})^2}{n}}$ ，其中平均值

$\bar{x}=\frac{\sum_{i=1}^nx_i}{n}$ ，x

_i为第i块矩形棋盘的总分。

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

Input

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

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

Output

仅一个数，为O'（四舍五入精确到小数点后三位）。

Sample Input

31 1 1 1 1 1 1 31 1 1 1 1 1 1 11 1 1 1 1 1 1 11 1 1 1 1 1 1 11 1 1 1 1 1 1 11 1 1 1 1 1 1 11 1 1 1 1 1 1 01 1 1 1 1 1 0 3

Sample Output

1.633

Source

题解：

首先将原式化简为 ∑xi^2 - （平均值的平方）而平均值是已知的所以为我们只要球前者就可以

每一刀，我们只能按 x轴方向切或 y 方向切

用 dp[k][x1][y1][x2][y2] 表示将以 x1,y1,为左上角，x2,y2，为右下角的矩形分成 k 分的最小值

s[x1][y1][x2][y2] 表示以 x1,y1,为左上角，x2,y2，为右下角的矩形的平方

状态转移为

dp[k][x1][y1][x2][y2] = min(dp[k - 1][x1][y1][ i ][y2]) + s[i+1][y1][x2][y2], dp[k - 1][x1][y1][i + 1][y2] + s[x1][y1][i][y2]) （沿 x 轴切）

min(dp[k - 1][x1][y1][ x2][i]) + s[x1][i + 1][x2][y2], dp[k - 1][x1][i + 1][x2][y2] + s[x1][y1][x2][ i ]);

代码：

View Code

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 #include
             8 #include
             
               9 #include
              
                10 #include
               
                 11 #define Min(a,b) a
                
                 b?a:b 13 #define CL(a,num) memset(a,num,sizeof(a)); 14 #define maxn 205 15 #define eps 1e-6 16 #define inf 9999999 17 #define mx 1<<60 18 19 using namespace std; 20 21 double mat[10][10]; 22 double dp[20][10][10][10][10]; 23 double s[10][10][10][10] ; 24 25 void init() 26 { 27 int i,j,k,l; 28 double sum = 0; 29 30 for( i = 1;i <= 8;++i) 31 { 32 for( j = i; j <= 8 ;++j) 33 { 34 35 for(k = 1 ; k <= 8; ++k ) 36 { 37 sum = 0; 38 39 for(l = k ; l <= 8 ;++l) 40 { 41 sum += mat[l][j] - mat[l][i - 1] ; 42 s[k][i][l][j] = sum*sum; 43 44 } 45 46 47 } 48 49 } 50 } 51 52 53 } 54 double dfs(int k,int x1,int y1,int x2,int y2) 55 { 56 57 int i; 58 double tmp ; 59 60 61 if(dp[k][x1][y1][x2][y2] >= eps ) return dp[k][x1][y1][x2][y2] ; 62 63 if( k == 1) 64 { 65 dp[k][x1][y1][x2][y2] = s[x1][y1][x2][y2] ; 66 return dp[k][x1][y1][x2][y2] ; 67 } 68 else 69 { 70 double ans = inf ; 71 for(i = x1; i < x2; ++i) 72 { 73 tmp = min(dfs(k - 1,x1,y1, i,y2) + s[i+1][y1][x2][y2],dfs(k - 1,i+1,y1,x2,y2) + s[x1][y1][i][y2]); 74 ans = min(ans,tmp); 75 } 76 77 for(i = y1; i < y2 ; ++i ) 78 { 79 tmp = min(dfs(k - 1,x1,y1,x2,i) + s[x1][i + 1][x2][y2],dfs(k - 1,x1,i+1,x2,y2) + s[x1][y1][x2][i]); 80 ans = min(ans,tmp); 81 } 82 83 dp[k][x1][y1][x2][y2] = ans ; 84 85 return dp[k][x1][y1][x2][y2]; 86 87 88 } 89 } 90 int main() 91 { 92 int n,i,j; 93 double a; 94 //freopen("data.in","r",stdin); 95 scanf("%d",&n); 96 97 double cnt = 0; 98 99 100 for( i = 1;i <= 8;++i )101 {102 double sum = 0;103 for( j = 1; j <= 8 ;++j)104 {105 scanf("%lf",&a);106 sum += a;107 cnt +=a;108 mat[i][j] = sum ;109 }110 }111 112 113 114 115 116 117 init();118 119 double k = cnt/(n*1.0);120 121 double ans = dfs(n,1,1,8,8);122 123 ans = (ans/(n*1.0)) - k*k ;124 125 ans = sqrt(ans);126 printf("%.3lf\n",ans);127 128 }

转载于:https://www.cnblogs.com/acSzz/archive/2012/08/11/2633325.html

你可能感兴趣的文章

ssh The authenticity of host '10.11.26.2 (10.11.26.2)' can't be established