http://poj.org/problem?id=1191
dp
# include <stdio.h>
# include <string.h>
# include <math.h>
# define M (8 + 3)
# define N (14 + 3)
# define INF 1000000000
int n, m = 8;
int a[M][M];
int s[M][M];
int f[N][M][M][M][M];
int Min(int x, int y) {
return x<y ? x:y;
}
int cal(int x1, int y1, int x2, int y2)
{
int ret = s[x2][y2]+s[x1-1][y1-1]-s[x1-1][y2]-s[x2][y1-1];
return ret * ret;
}
void pre(void)
{
int i, j, t;
for (i = 1; i <= m; ++i)
for (j = 1; j <= m; ++j)
scanf("%d", &a[i][j]);
for (i = 0; i < N; ++i)
s[i][0] = s[0][i] = 0;
for (i = 1; i <= m; ++i)
{
t = 0;
for (j = 1; j <= m; ++j)
{
t += a[i][j];
s[i][j] = t + s[i-1][j];
}
}
memset(f, -1, sizeof(f));
}
int dp(int k, int x1, int y1, int x2, int y2)
{
int i, j;
int & ans = f[k][x1][y1][x2][y2];
if (ans != -1)return ans;
if (k == 1) return ans = cal(x1, y1, x2, y2);
ans = INF;
for (i = x1; i < x2; ++i)
ans = Min( ans, Min( dp(k-1, x1, y1, i, y2)+cal(i+1, y1, x2, y2),
dp(k-1, i+1, y1, x2, y2)+cal(x1, y1, i, y2) ) );
for (j = y1; j < y2; ++j)
ans = Min( ans, Min( dp(k-1, x1, y1, x2, j)+cal(x1, j+1, x2, y2),
dp(k-1, x1, j+1, x2, y2)+cal(x1, y1, x2, j) ) );
return ans;
}
void solve(void)
{
double ans;
ans = ( 1.0*dp(n, 1, 1, 8, 8) )/( 1.0*n )
- (1.0*s[8][8]/n)*(1.0*s[8][8]/n);
printf("%.3f\n", sqrt(ans) );
}
int main()
{
scanf("%d", &n);
pre();
solve();
return 0;
}
posted on 2012-10-11 12:14
yajunw 阅读(185)
评论(0) 编辑 收藏 引用