AcWing 321 棋盘分割题解

很水的题但是第一次写二维区间 dp 代码略显恶心所以水一篇博客

link

将一个 $8\times8$ 的棋盘进行如下分割：将原棋盘沿矩形边分割成两部分，再将其中一部分继续如此分割，割 $n−1$ 次后得到 $n$ 块矩形棋盘。

第 $(i, j)$ 的格子有分值 $a_{i, j}$，第 $i$ 块棋盘的分值 $x_i$ 为棋盘的分值和。要求输出方差 $\sigma$ 的最小值。

方差 $\sigma = \sqrt{\dfrac{\sum_{i=1}^n (x_i - \bar{x})^2}{n}}$，平均值 $\bar{x}=\dfrac{\sum_{i=1}^n x_i}{n}$。

$1 \le n \le 15$，$0 \le a_{i, j} \le 100$。

$f_{d, i, j, k, l}$ 表示 $(i, j)$ 到 $(k, l)$ 的矩形棋盘分割 $d$ 次的最小 $\sigma ^ 2 n$。

区间 dp 需要先枚举长度才能保证正确性。

各种原因导致我的代码极丑。

#include <bits/stdc++.h>
using namespace std;

inline int read() {
    int x = 0, f = 0; char c = 0;
    while (!isdigit(c)) f |= c == '-', c = getchar();
    while (isdigit(c)) x = (x << 3) + (x << 1) + (c & 15), c = getchar();
    return f ? -x : x;
}

#define rep(i, a, b) for (int i = (a); i <= (b); i ++)

#define N 10
#define M 20
#define INF 1e9

int n, m, a[N][N], s[N][N];
double f[M][N][N][N][N];

int main() {
    n = 8, m = read() - 1;
    rep(i, 1, n) rep(j, 1, n) s[i][j] = a[i][j] = read();
    rep(i, 1, n) rep(j, 1, n) s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];

    double bX = 1.0 * s[n][n] / (m + 1);
    rep(i, 1, n) rep(j, 1, n) rep(k, i, n) rep(l, j, n) {
        f[0][i][j][k][l] = s[k][l] - s[i - 1][l] - s[k][j - 1] + s[i - 1][j - 1] - bX;
        f[0][i][j][k][l] = f[0][i][j][k][l] * f[0][i][j][k][l];
    }

    rep(d, 1, m) rep(len, 1, n) rep(i, 1, n) rep(j, 1, n) {
        auto F = [&f, &s](int d, int i, int j, int k, int l) {
            double &now = f[d][i][j][k][l]; now = INF;
            rep(a, i, k - 1) {
                now = min(now, f[d - 1][i][j][a][l] + f[0][a + 1][j][k][l]);
                now = min(now, f[0][i][j][a][l] + f[d - 1][a + 1][j][k][l]);
            }
            rep(b, j, l - 1) {
                now = min(now, f[d - 1][i][j][k][b] + f[0][i][b + 1][k][l]);
                now = min(now, f[0][i][j][k][b] + f[d - 1][i][b + 1][k][l]);
            }
        };
        if (j + len - 1 <= n) rep(k, i, n) F(d, i, j, k, j + len - 1);
        if (i + len - 1 <= n) rep(l, j, n) F(d, i, j, i + len - 1, l);
    }

    printf("%.3lf\n", sqrt(f[m][1][1][n][n] / (m + 1)));
    return 0;
}