1191: 棋盘分割
总时间限制:
1000ms
内存限制:
65536kB
描述
将一个8*8的棋盘进行如下分割: 将原棋盘割下一块矩形棋盘并使剩下部分也是矩形, 再将剩下的部分继续如此分割, 这样割了 (n-1) 次后, 连同最后剩下的矩形棋盘共有 n 块矩形棋盘.(每次切割都只能沿着棋盘格子的边进行)
原棋盘上每一格有一个分值, 一块矩形棋盘的总分为其所含各格分值之和. 现在需要把棋盘按上述规则分割成 n 块矩形棋盘, 并使各矩形棋盘总分的均方差最小.
均方差, 其中平均值,xi 为第 i 块矩形棋盘的总分.
请编程对给出的棋盘及 n, 求出 O'的最小值.
输入
第 1 行为一个整数 n(1 <n < 15).
第 2 行至第 9 行每行为 8 个小于 100 的非负整数, 表示棋盘上相应格子的分值. 每行相邻两数之间用一个空格分隔.
输出
仅一个数, 为 O'(四舍五入精确到小数点后三位).
样例输入
- 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
样例输出
1.633
这一题首先对公式进行化简. 求方差的公式可以这样化简:
由图可见, 求方差最小值及为求各部分权值平方和的最小值. 可以用动态规划.
AC 代码贴在下面
- #include<iostream>
- #include<map>
- #include<string>
- #include<cmath>
- #include<iomanip>
- #include<algorithm>
- #include<memory.h>
- using namespace std;
- int dp[15][15][15][15][15];// 动态规划数组, 记录状态
- int m[10][10];
- int sum[15][15] = { 0 };// 从左上角 (1,1) 到(i,j)的棋盘的权值之和及 sum[i][j]
- int Sum = 0;
- int n;
- int calsum(int x1, int y1, int x2, int y2)// 计算从 (x1,y1) 到(x2,y2)的棋盘的权值之和
- {
- return (sum[x2][y2] - sum[x2][y1 - 1] - sum[x1 - 1][y2] + sum[x1 - 1][y1 - 1]);
- }
- int solve(int n, int x1, int y1, int x2, int y2)// 递归函数, n 表示当前部分还能分割成多少块, x1,y1,x2,y2 分别表示当前棋盘左上角和右下角的坐标
- {
- // 该函数返回剩余分割成 n 块的从 (x1,y1) 到(x2,y2)的棋盘内部 n 块被分割棋盘的方差的平方和的最小值
- int t, a, b, c, e;
- int ma = 1e7;
- int& ans = dp[n][x1][y1][x2][y2];// 注意这里 ans 用引用形式, ans 改变时, 相应的 dp 值也发生改变
- if (ans != -1)//ans 非负表示 dp 值已经记录, 可以直接引用, 节省时间
- {
- return ans;
- }
- if (n == 1)//n=1 时, 达到边界条件
- {
- t = calsum(x1, y1, x2, y2);
- ans = t * t;
- return ans;
- }
- for (a = x1; a <x2; a++)// 从 x 方向进行分割
- {
- c = calsum(a + 1, y1, x2, y2);
- e = calsum(x1, y1, a, y2);
- t = min(c*c + solve(n - 1, x1, y1, a, y2), e*e + solve(n - 1, a + 1, y1, x2, y2));// 从分别对左右侧进行接下来的分割中选择最小值
- if (ma> t)
- {
- ma = t;
- }
- }
- for (b = y1; b <y2; b++)// 同上, 不过这次是从 y 方向进行分割
- {
- c = calsum(x1, b + 1, x2, y2);
- e = calsum(x1, y1, x2, b);
- t = min(c*c + solve(n - 1, x1, y1, x2, b), e*e + solve(n - 1, x1, b + 1, x2, y2));
- if (ma> t)
- {
- ma = t;
- }
- }
- ans = ma;
- return ma;
- }
- int main()
- {
- memset(dp, -1, sizeof(dp));// 一开始全部赋成 - 1
- cin>> n;
- for (int i = 1; i <= 8; i++)
- {
- Sum = 0;//Sum 记录棋盘每一行的权值
- for (int j = 1; j <= 8; j++)
- {
- cin>> m[i][j];
- Sum += m[i][j];
- sum[i][j] += sum[i - 1][j] + Sum;
- }
- }
- double result = n * solve(n, 1, 1, 8, 8) - sum[8][8] * sum[8][8];
- cout << setiosflags(iOS::fixed) << setprecision(3) << sqrt(result / (n*n)) << endl;// 按照公式计算
- return 0;
- }
革命尚未成功, 同志仍需努力.
来源: http://www.bubuko.com/infodetail-3415842.html