哪个网站可以做服装批发/免费建立个人网站凡科

总时间限制: 

1000ms

内存限制: 

65536kB

描述

将一个８*８的棋盘进行如下分割：将原棋盘割下一块矩形棋盘并使剩下部分也是矩形，再将剩下的部分继续如此分割，这样割了(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

来源

Noi 99

#include <iostream>
#include <math.h>
#include <string.h>
#include <algorithm>#define INF 0x3f3f3f3fusing namespace std;
int n;
double dp[10][10][10][10][17];
int fen[9][9], sum[9][9];double getxi2(int i1, int j1, int i2, int j2){return  pow(1.0*sum[i2][j2]-sum[i1-1][j2]-sum[i2][j1-1]+sum[i1-1][j1-1], 2);
}
double mind(double a, double b){return a < b ? a : b;
}int main()
{scanf("%d", &n);for (int i = 1; i <= 8;i++)for (int j = 1; j <= 8; j++)scanf("%d", &fen[i][j]);memset(sum, 0, sizeof sum);memset(dp, 0, sizeof dp);for (int i = 1; i <= 8;i++)for (int j = 1; j <= 8; j++){sum[i][j] = sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1] + fen[i][j];}for (int i1 = 1; i1 <= 8;i1++)for (int j1 = 1; j1 <= 8;j1++)for (int i2 = i1; i2 <= 8;i2++)for (int j2 = j1; j2 <= 8; j2++){dp[i1][j1][i2][j2][0] = getxi2(i1, j1, i2, j2);}for (int i = 1; i <= n-1; i++)//I表示 切i 刀;for (int i1 = 1; i1 <= 8; i1++)for (int j1 = 1; j1 <= 8; j1++)for (int i2 = i1; i2 <= 8; i2++)for (int j2 = j1; j2 <= 8; j2++){dp[i1][j1][i2][j2][i] = INF;for (int k = i1; k < i2; k++){//横切dp[i1][j1][i2][j2][i] = mind(dp[i1][j1][i2][j2][i], mind(dp[i1][j1][k][j2][0] + dp[k + 1][j1][i2][j2][i - 1], dp[i1][j1][k][j2][i - 1] + dp[k+1][j1][i2][j2][0]));}for (int k = j1; k < j2; k++){//竖切dp[i1][j1][i2][j2][i] = mind(dp[i1][j1][i2][j2][i], mind(dp[i1][j1][i2][k][0] + dp[i1][k + 1][i2][j2][i - 1], dp[i1][j1][i2][k][i - 1] + dp[i1][k + 1][i2][j2][0]));}}printf("%.3lf", sqrt(dp[1][1][8][8][n-1]/n-pow(1.0*sum[8][8]/n,2)));return 0;
}