LYDSY 1048
题目大意
暂无
题目解法
暂无
RTFC
#include <cmath>
#include <cstdio>
#include <cstring>
inline double min(double a, double b) { return a < b ? a : b; }
int a, b, n;
double g[11][11], sum[11][11], f[11][11][11][11][11], avg;
double dfs(int x1, int y1, int x2, int y2, int v)
{
if (f[x1][y1][x2][y2][v] < f[0][0][0][0][0] - 100)
return f[x1][y1][x2][y2][v];
else if (v == 0)
return f[x1][y1][x2][y2][v] =
(sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1] - avg) *
(sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1] - avg);
else
{
double ans = *****f;
for (int i = x1; i < x2; i++)
for (int j = 0; j < v; j++)
ans = min(ans, dfs(x1, y1, i, y2, j) + dfs(i + 1, y1, x2, y2, v - j - 1));
for (int i = y1; i < y2; i++)
for (int j = 0; j < v; j++)
ans = min(ans, dfs(x1, y1, x2, i, j) + dfs(x1, i + 1, x2, y2, v - j - 1));
return f[x1][y1][x2][y2][v] = ans;
}
}
int main()
{
memset(f, 0x7f, sizeof(f));
scanf("%d%d%d", &a, &b, &n);
for (int i = 1; i <= a; i++)
for (int j = 1; j <= b; j++)
scanf("%lf", &g[i][j]);
for (int i = 1; i <= a; i++)
for (int j = 1; j <= b; j++)
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + g[i][j];
avg = sum[a][b] / n;
printf("%.2f", sqrt(dfs(1, 1, a, b, n - 1) / n));
return 0;
}