POJ1191――棋盘分割 - c++编程基础

棋盘分割

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 12456		Accepted: 4389

Description

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

原棋盘上每一格有一个分值，一块矩形棋盘的总分为其所含各格分值之和。现在需要把棋盘按上述规则分割成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

刘汝佳黑书的题，方法书上写的很详细，就不赘述了，这应该算是一类二维区间dp吧

#include 
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               using namespace std; const int inf = 0x3f3f3f3f; int dp[20][10][10][10][10]; int D[10][10][10][10]; int mat[20][20]; int sum[20][20]; int main() { int n; while (~scanf("%d", &n)) { double _x = 0; memset (sum, 0, sizeof(sum)); memset (dp, inf, sizeof(dp)); for (int i = 1; i <= 8; ++i) { for (int j = 1; j <= 8; ++j) { scanf("%d", &mat[i][j]); } for (int j = 1; j <= 8; ++j) { sum[i][j] += sum[i][j - 1] + mat[i][j]; } } for (int j = 1; j <= 8; ++j)//预处理 { for (int i = 1; i <= 8; ++i) { sum[i][j] += sum[i - 1][j]; } } for (int i = 1; i <= 8; ++i) { for (int j = 1; j <= 8; ++j) { for (int k = i; k <= 8; ++k) { for (int l = j; l <= 8; ++l) { D[i][j][k][l] = sum[k][l] - sum[k][j - 1] - sum[i - 1][l] + sum[i - 1][j - 1]; // printf("D[%d][%d][%d][%d] = %d\n", i, j, k, l, D[i][j][k][l]); D[i][j][k][l] *= D[i][j][k][l]; } } } } _x = sum[8][8] * 1.0 / n; _x *= _x; for (int i = 1; i <= 8; ++i) { for (int j = 1; j <= 8; ++j) { for (int k = i; k <= 8; ++k) { for (int l = j; l <= 8; ++l) { dp[0][i][j][k][l] = D[i][j][k][l]; } } } } for (int i = 1; i < n; ++i) { for (int j = 1; j <= 8; ++j)/*x1*/ { for (int k = 1; k <= 8; ++k)/*y1*/ { for (int l = j; l <= 8; ++l)/*x2*/ { for (int p = k; p <= 8; ++p)/*y2*/ { for (int q = j; q < l; ++q) { dp[i][j][k][l][p] = min(min(dp[i][j][k][l][p], dp[i - 1][j][k][q][p] + D[q + 1][k][l][p]), dp[i - 1][q + 1][k][l][p] + D[j][k][q][p]); } for (int q = k; q < p; ++q) { dp[i][j][k][l][p] = min(min(dp[i][j][k][l][p], dp[i - 1][j][k][l][q] + D[j][q + 1][l][p]), dp[i - 1][j][q + 1][l][p] + D[j][k][l][q]); } } } } } } double t = dp[n - 1][1][1][8][8] * 1.0 / n; printf("%.3f\n", sqrt(t - _x)); } return 0; }