posts - 16,comments - 0,trackbacks - 0
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<? 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, 
-1sizeof(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 == 1return 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, 1188) )/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 阅读(169) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理