棋牌麻将 - 米需爱网 - 老鼠爱大米,人人需要爱!
Copyright & 2014
Corporation, All Rights Reserved
Processed in 0.0137 second(s), 1 db_queries,
0 rpc_queries大一的时候接触这道题目，当时死活不会做。。。最近突然又想起了这个伤疤，就把这道题给秒杀掉了，想想当年的我真是笨到家了T_T
首先对表达式进行变形，不考虑常量，最终其实就是求分成n块，使得每块的分值平方和最小。
基本思想很简单了，用dp[r1][c1][r2][c2][n]表示r1行到r2行、c1列到c2列的矩形区域切n刀得到的最小平方和，n=0时是一个边界条件，对于n&0的情形，分纵切和横切两种情况，对每一种情况，对左（上）半部分或者右（下）半部分继续切n-1刀，取四种情况的最小值就可以了。
#include &stdio.h&
#include &string.h&
#include &algorithm&
#include &cassert&
#include &cmath&
#include &limits.h&
#define FOR(i, n) for (int i = 0; i & ++i)
int arr[9][9], sm[9][9];
int dp[9][9][9][9][16];
// get the square of sum in this region
int get(int r1, int c1, int r2, int c2) {
assert(r1 &= r2 && c1 &= c2);
int res = sm[r2][c2] - sm[r2][c1 - 1] - sm[r1 - 1][c2] + sm[r1 - 1][c1 - 1];
return res *
const int INF = INT_MAX / 4;
int solve(int r1, int c1, int r2, int c2, int n) {
assert(n &= 0);
if (dp[r1][c1][r2][c2][n] != -1) return dp[r1][c1][r2][c2][n];
if (r1 & r2 || c1 & c2) return INF;
if (n == 0) return get(r1, c1, r2, c2);
// can not be divided anymore
if (r1 == r2 && c1 == c2) return INF;
int mn = INF;
// split in column
for (int c = c1; c & c2; ++c) {
// continue to split on right part
mn = min(mn, get(r1, c1, r2, c) + solve(r1, c + 1, r2, c2, n - 1));
// continue to split on left part
mn = min(mn, solve(r1, c1, r2, c, n - 1) + get(r1, c + 1, r2, c2));
// split in row
for (int r = r1; r & r2; ++r) {
// continue to split on bottom part
mn = min(mn, get(r1, c1, r, c2) + solve(r + 1, c1, r2, c2, n - 1));
// continue to split on top part
mn = min(mn, solve(r1, c1, r, c2, n - 1) + get(r + 1, c1, r2, c2));
dp[r1][c1][r2][c2][n] =
int main() {
int N, total = 0;
scanf(&%d&, &N);
memset(arr, 0, sizeof(arr));
memset(sm, 0, sizeof(sm));
FOR(i, 8) FOR(j, 8) {
scanf(&%d&, arr[i + 1] + j + 1);
total += arr[i + 1][j + 1];
for (int i = 1; i &= 8; ++i)
for (int j = 1; j &= 8; ++j)
sm[i][j] = sm[i - 1][j] + sm[i][j - 1] - sm[i - 1][j - 1] + arr[i][j];
memset(dp, -1, sizeof(dp));
double res = solve(1, 1, 8, 8, N - 1) - static_cast&double&(total * total) / N;
res = sqrt(res / N);
// answer for sample: 1.633
printf(&%.3f\n&, res);
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：123793次
积分：2553
积分：2553
排名：第6264名
原创：122篇
转载：80篇
评论：41条
北大小硕，各种渣。。。
(4)(1)(2)(11)(5)(5)(2)(4)(4)(2)(3)(4)(2)(3)(3)(4)(3)(6)(8)(4)(6)(13)(2)(6)(8)(6)(13)(5)(12)(4)(6)(12)(13)(6)(11)(1)算法合集之《浅谈棋盘的分割思想》_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
评价文档：
喜欢此文档的还喜欢
算法合集之《浅谈棋盘的分割思想》
算​法​合​集
阅读已结束，如果下载本文需要使用
想免费下载本文？
把文档贴到Blog、BBS或个人站等：
普通尺寸(450*500pix)
较大尺寸(630*500pix)
你可能喜欢1012人阅读
题目连接：
解题思路：
棋盘分割一块之后，剩余的棋盘的分割和原问题类似，只是规模变小了。棋盘分割问题可以采用动态规划方法解决。
对方差公式进行化解，得到σ^2=1/n∑xi^2 - x^2
可知，要使方差最小，只需使∑xi^2最小即可，即各块分值平方和最小。平均值&x是个固定的数，跟分割的方式没有关系，
首先定义状态：dp[k][x1][y1][x2][y2]，表示左上角坐标(x1,y1)到右下角坐标(x2,y2)区域的棋盘经过k次分割后，各块分值平方和的最小值。则状态转移方程为：
dp[k][x1][y1][x2][y2] = min{
dp[0][x1][y1][t][y2]+dp[k-1][t+1][y1][x2][y2], (x1 &= t & x2)
dp[k-1][x1][y1][t][y2]+dp[0][t+1][y1][x2][y2], (x1 &= t & x2) &//竖切
dp[0][x1][y1][x2][t]+dp[k-1][x1][t+1][x2][y2], (y1 &= t & y2)
dp[k-1][x1][y1][x2][t]+dp[0][x1][t+1][x2][y2]&(y1 &= t & y2) //横切
dp[0][x1][y1][x2][y2]表示左上角坐标(x1,y1)到右下角坐标(x2,y2)区域的棋盘的分值和平方
有了状态转移方程后，就很容易写出代码了，开始dp数组使用long double，提交后WA，改成double后就AC了，很奇怪。
#include &iostream&
#include &cstdio&
#include &cmath&
#include &iomanip&
int data[9][9];
int sum[9][9];
double dp[14][9][9][9][9];
//返回左上角坐标(x1,y1)到右下角坐标(x2,y2)区域的棋盘的分值和平方
double count(int x1, int y1, int x2, int y2)
double ans = (double)(sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1]);
return ans*
int main()
int n, total=0;
//输入数据
for(int i=1; i&=8; ++i)
for(int j=1; j&=8; ++j)
cin&&data[i][j];
//sum[i][j]表示棋盘(1,1)到(i,j)区域的累计分值
sum[i][j] = sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1] + data[i][j];
//total表示整个棋盘的分值之和
total += data[i][j];
//初始化dp数组
for(int x1=1; x1&=8; ++x1)
for(int y1=1; y1&=8; ++y1)
for(int x2=x1; x2&=8; ++x2)
for(int y2=y1; y2&=8; ++y2)
dp[0][x1][y1][x2][y2] = count(x1,y1,x2,y2);
//自底向上计算dp数据
for(int k=1; k&n; ++k)
for(int x1=1; x1&=8; ++x1)
for(int y1=1; y1&=8; ++y1)
for(int x2=x1; x2&=8; ++x2)
for(int y2=y1; y2&=8; ++y2)
dp[k][x1][y1][x2][y2] = (double)(1&&30);
for(t=x1; t&x2; ++t)
dp[k][x1][y1][x2][y2] = min(dp[k][x1][y1][x2][y2], dp[0][x1][y1][t][y2]+dp[k-1][t+1][y1][x2][y2]);
dp[k][x1][y1][x2][y2] = min(dp[k][x1][y1][x2][y2], dp[k-1][x1][y1][t][y2]+dp[0][t+1][y1][x2][y2]);
for(t=y1; t&y2; ++t)
dp[k][x1][y1][x2][y2] = min(dp[k][x1][y1][x2][y2], dp[0][x1][y1][x2][t]+dp[k-1][x1][t+1][x2][y2]);
dp[k][x1][y1][x2][y2] = min(dp[k][x1][y1][x2][y2], dp[k-1][x1][y1][x2][t]+dp[0][x1][t+1][x2][y2]);
//计算方差平方
double ans = dp[n-1][1][1][8][8]*1.0/n - ((double)total*1.0/n)*((double)total*1.0/n);
//输出方差,精确到小数点后三位
cout&&setprecision(3)&&fixed&&sqrt(ans)&&
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：41856次
排名：千里之外
原创：55篇
评论：10条
(2)(1)(2)(9)(16)(14)(1)(1)(1)(5)(3)