思路
-
首先,我们要弄明白题中的方差是什么。
公式:$S = \sqrt{\frac{1}{n} \sum_{i=1}^{n} (x_i - \bar{x})^2}$
-
接下来,我们思考一下题目怎么做。
数据很小,于是想到了暴搜。
但是时间复杂度有点难以接受啊,优化一下吧。
有一种很有效的优化,那就是广为人知的记忆化搜索。它能使所有重复的操作只做一次,大大降低了时间复杂度。
下面我们来看看框架。
用 $f[i][sx][tx][sy][ty]$ 表示分割 $i$ 次,操作范围为左上角在 $(sx,sy)$ 右下角在 $(tx,ty)$ 的矩阵得到 $\sum_{i=1}^{n} (x_i - \bar{x})^2$ 的最小值。很容易想到,dfs 函数的参数就也是这五个值了。
那么函数出口是什么情况呢?
$i=0$ 的时候返回矩阵里所有元素之和,我们可以用二维前缀和来预处理。
函数内部呢?
如果已经存过答案了,那么返回 $f[i][sx][tx][sy][ty]$ 。否则枚举切断的位置及两边分配的分割次数并递归求解。
代码
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const double INF = 1e300; // 初始值,极大值
int n, m, k;
int a[25][25];
double s[25][25], avg; // 二维前缀和,平均值
double f[25][25][25][25][25]; // 记忆化数组
double dfs(int num, int sx, int tx, int sy, int ty) // 递归函数
{
if (sx > tx || sy > ty || num < 0) // 错误的情况
return 0;
if (f[num][sx][tx][sy][ty] != INF) // 如果存过了
return f[num][sx][tx][sy][ty]; // 直接返回
if (num == 0) // 出口
{
double sum = s[tx][ty] - s[sx - 1][ty] - s[tx][sy - 1] + s[sx - 1][sy - 1];
sum = (sum - avg) * (sum - avg);
return f[num][sx][tx][sy][ty] = sum;
}
for (int i = sx; i < tx; i++) // 分割位置
for (int j = 0; j < num; j++) // 次数分配
f[num][sx][tx][sy][ty] = min(f[num][sx][tx][sy][ty], dfs(j, sx, i, sy, ty) + dfs(num - j - 1, i + 1, tx, sy, ty));
for (int i = sy; i < ty; i++) // 分割位置
for (int j = 0; j < num; j++) // 次数分配
f[num][sx][tx][sy][ty] = min(f[num][sx][tx][sy][ty], dfs(j, sx, tx, sy, i) + dfs(num - j - 1, sx, tx, i + 1, ty));
return f[num][sx][tx][sy][ty];
}
int main()
{
for (int i = 0; i <= 24; i++)
for (int sx = 0; sx <= 24; sx++)
for (int tx = 0; tx <= 24; tx++)
for (int sy = 0; sy <= 24; sy++)
for (int ty = 0; ty <= 24; ty++)
f[i][sx][sy][tx][ty] = INF; // 初值
cin >> n >> m >> k;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
cin >> a[i][j];
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j]; // 预处理
}
avg = s[n][m] / k; // 平均值
double ans = sqrt(dfs(k - 1, 1, n, 1, m) / k);
printf("%.2lf\n", ans); // 别忘了位数
return 0;
}
标签:sy,sx,tx,ty,int,题解,HAOI2007,num,P2217
From: https://www.cnblogs.com/thrift/p/18591516