以下文章来源于小K算法 ，作者小K算法
小K算法 .
曾就职华为和美团，中山大学数学与计算机系本科，专注分享数学、算法、科学等硬核知识
来自公众号：小K算法
1.为什么全局最优解可以转化为子问题的最优解呢？
上面的分割方法，在每一个阶段，我们已经把所有可能的分割方法全部枚举完了，那其中的最优肯定就是当前阶段的最优了，因为没有其它的可能性。
这就是一个无后效性，因为我们只需要分割的分值平方和最小，并不关心它具体是怎么分割的。之前怎么分割，在当前阶段看来都是一样的，不受影响。
#define N 9
int chessboard[N][N];
int d[2][N][N][N][N];
int sum[N][N] = {0};
int getSum(int x, int y, int k, int l) {
int ans = sum[k][l] - sum[k][y - 1] - sum[x - 1][l] + sum[x - 1][y - 1];
return ans * ans;
}
int min(int x, int y) {
return x < y ? x : y;
}
void init() {
for (int i = 1; i <= 8; ++i) {
for (int j = 1; j <= 8; ++j) {
cin >> chessboard[i][j];
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + chessboard[i][j];
}
}
for (int i = 1; i < N; ++i) {
for (int j = 1; j < N; ++j) {
for (int k = i; k < N; ++k) {
for (int l = j; l < N; ++l) {
d[0][i][j][k][l] = getSum(i, j, k, l);
}
}
}
}
}
int main() {
int n;
cin >> n;
init();
int s = 0;
for (int t = 1; t < n; ++t) {
s = 1 - s;
// 枚举起点
for (int i = 1; i < N; ++i) {
for (int j = 1; j < N; ++j) {
// 枚举终点
for (int k = i; k < N; ++k) {
for (int l = j; l < N; ++l) {
d[s][i][j][k][l] = 1e8;
// 横切
for (int a = i; a < k; ++a) {
d[s][i][j][k][l] = min(d[s][i][j][k][l], d[1 - s][i][j][a][l] + getSum(a + 1, j, k, l));
d[s][i][j][k][l] = min(d[s][i][j][k][l], d[1 - s][a + 1][j][k][l] + getSum(i, j, a, l));
}
// 纵切
for (int b = j; b < l; ++b) {
d[s][i][j][k][l] = min(d[s][i][j][k][l], d[1 - s][i][j][k][b] + getSum(i, b + 1, k, l));
d[s][i][j][k][l] = min(d[s][i][j][k][l], d[1 - s][i][b + 1][k][l] + getSum(i, j, k, b));
}
}
}
}
}
}
double average = sum[N - 1][N - 1] * 1.0 / n;
double ans = d[s][1][1][8][8] * 1.0 / n - average * average;
printf("%.3lf", sqrt(ans));
return 0;
}
网友评论已有0条评论, 我也要评论