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 閱讀(208)
評(píng)論(0) 編輯 收藏 引用