poj 1191 棋盘分割（dp）

好纠结的一道题啊，一开始写错了个字母，跳了半天，后来脚上去竟然不对，，看了 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

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

Sample Output

1.633

Source

Noi 99

题解：

首先将原式化简为 ∑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<cstdio>
  2 #include<cstring>
  3 #include<cmath>
  4 #include<iostream>
  5 #include<algorithm>
  6 #include<set>
  7 #include<map>
  8 #include<queue>
  9 #include<vector>
 10 #include<string>
 11 #define Min(a,b) a<b?a:b
 12 #define Max(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 }

poj 1191 棋盘分割 （dp）

poj 1191 棋盘分割（dp）