不错的DP题。状态f[i][x1][y1][x2][y2]表示要把(x1,y1) -- (x2, y2) 分割成i块所得到的最小平方和(平方和指的是每块矩形的和的平方和)。然后根据水平和竖直切割进行状态转移。这样计算出f[n][1][1][8][8]得到整个棋盘分割成n块得到的最小平方和,然后代入均方差公式算得结果。


/*************************************************************************
Author: WHU_GCC
Created Time: 2007-10-1 19:01:11
File Name: pku1191.cpp
Description: 
***********************************************************************
*/

#include 
<iostream>
#include 
<cmath>
using namespace std;

#define out(x) (cout << #x << ": " << x << endl)
typedef 
long long int64;
const int maxint = 0x7FFFFFFF;
const int64 maxint64 = 0x7FFFFFFFFFFFFFFFLL;
template 
<class T> void show(T a, int n) for (int i = 0; i < n; ++i) cout << a[i] << ' '; cout << endl; }
template 
<class T> void show(T a, int r, int l) for (int i = 0; i < r; ++i) show(a[i], l); cout << endl; }

int n;
int a[9][9], g[9][9];
int f[16][9][9][9][9];

inline 
int sum(int x1, int y1, int x2, int y2)
{
    
return (g[x2][y2] - g[x1 - 1][y2] - g[x2][y1 - 1+ g[x1 - 1][y1 - 1])
        
* (g[x2][y2] - g[x1 - 1][y2] - g[x2][y1 - 1+ g[x1 - 1][y1 - 1]);
}


int dp(int k, int x1, int y1, int x2, int y2)
{
    
if (f[k][x1][y1][x2][y2] != maxint)
        
return f[k][x1][y1][x2][y2];
    
if (k == 1)
        
return f[k][x1][y1][x2][y2] = sum(x1, y1, x2, y2);
    
if (x1 == x2 && y1 == y2)
        
return f[k][x1][y1][x2][y2] = sum(x1, y1, x2, y2);
    
int ret = maxint;
    
for (int i = x1; i < x2; i++)
    
{
        ret 
<?= dp(k - 1, x1, y1, i, y2) + sum(i + 1, y1, x2, y2);
        ret 
<?= sum(x1, y1, i, y2) + dp(k - 1, i + 1, y1, x2, y2);
    }

    
for (int i = y1; i < y2; i++)
    
{
        ret 
<?= dp(k - 1, x1, y1, x2, i) + sum(x1, i + 1, x2, y2);
        ret 
<?= sum(x1, y1, x2, i) + dp(k - 1, x1, i + 1, x2, y2);
    }

    
return f[k][x1][y1][x2][y2] = ret;
}


int main()
{
    scanf(
"%d"&n);
    
for (int i = 1; i <= 8; i++)
        
for (int j = 1; j <= 8; j++)
            scanf(
"%d"&a[i][j]);
    memset(g, 
0sizeof(g));

    
for (int i = 0; i <= 8; i++)
        
for (int j = 0; j <= 8; j++)
            g[i][j] 
= g[i - 1][j] + g[i][j - 1- g[i - 1][j - 1+ a[i][j];
    
    
for (int k = 0; k <= 15; k++)
        
for (int x1 = 1; x1 <= 8; x1++)
            
for (int y1 = 1; y1 <= 8; y1++)
                
for (int x2 = 1; x2 <= 8; x2++)
                    
for (int y2 = 1; y2 <= 8; y2++)
                        f[k][x1][y1][x2][y2] 
= maxint;
    
    
double sum = 0.0;
    
for (int i = 1; i <= 8; i++)
        
for (int j = 1; j <= 8; j++)
            sum 
+= a[i][j];
    sum 
/= n;
    sum 
*= sum;

    printf(
"%.3lf\n", sqrt(dp(n, 1188/ double(n) - sum));
    
return 0;
}
posted on 2007-10-08 09:12 Felicia 阅读(784) 评论(1)  编辑 收藏 引用 所属分类: 动态规划
Comments

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理