poj1191 棋盘分割 dp

本题黑书P116有详细讲解。

思路:

先把方差公式化简:

σ2=1ni=1nx2i(x¯)2
其中平均数是一定的,就是方格里所有的数的和除以n,所以问题转化为将棋盘分成n个矩形,使每个矩形的总分的 平方和最小。

考虑左上角为(x1,y1),右下角为(x2,y2)的矩形:
设它的总分为s[x1, y1, x2, y2],切割k次得到k+1块矩形的总分平方和最小为d[x1, y1, x2, y2],则切一刀时,可以横着切,也可以竖着切,然后递归下去继续切即可。

代码:
#include cstdio
#include cstring
#include algorithm
#include iostream
#include cmath
#include climits

#define THIS (dp[k][x1][y1][x2][y2])

using namespace std;

int n;
int arr[11][11];
double sum[11][11];
double dp[17][11][11][11][11];

inline double S(int x1, int y1, int x2, int y2) {
    double t = sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1];
    return t * t;
}

double dfs(int k, int x1, int y1, int x2, int y2) {
    if (k == 1) {
        THIS = S(x1, y1, x2, y2);
        return THIS;
    }
    if (fabs(THIS)  1e-8) return THIS;
    THIS = 1  29;
    for (int i = x1; i  x2; i++) {
        THIS = min(THIS, min(dfs(k - 1, x1, y1, i, y2) + S(i + 1, y1, x2, y2),
            dfs(k - 1, i + 1, y1, x2, y2) + S(x1, y1, i, y2)));
    }
    for (int i = y1; i  y2; i++) {
        THIS = min(THIS, min(dfs(k - 1, x1, y1, x2, i) + S(x1, i + 1, x2, y2),
            dfs(k - 1, x1, i + 1, x2, y2) + S(x1, y1, x2, i)));
    }
    return THIS;
}

int main() {
    freopen("1191.in", "r", stdin);
    cin  n;
    for (int i = 1; i = 8; i++)
        for (int j = 1; j = 8; j++)
            cin  arr[i][j];
    for (int i = 1; i = 8; i++)
        for (int j = 1; j = 8; j++)
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + arr[i][j];
    double adv = sum[8][8] / n;
    double ans = dfs(n, 1, 1, 8, 8) / n;
    printf("%.3lf\n", sqrt(ans - adv * adv));
    return 0;
}
最新回复(0)
/jishudrOEx0_2BlOsy1LqAQjxUWKNS0N7PBNkfVgN5sVZ_2Fukrw_3D4858355
8 简首页