根据这2个公式可以 得到 O^2 = sum(x1^2 + x2^2 + x3^2 +...xi^2)/n - 平均值^2
所以我们就是要使得总分的平方和尽量小……
对于一次切割,可以横着切,可以竖着切,可以使剩下了的包含左上角,也可以使剩下了的包含右上角。
具体方程什么的看代码吧。
G++提交的时候记得把.3lf改成.3f
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
double sum[9][9];
double a[9][9];
int n;
double ave;
double d[16][9][9][9][9];
double s(int x1,int y1,int x2,int y2)
{
double tmp=sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1];
return tmp*tmp;
}
double dfs(int k,int x1,int y1,int x2,int y2)
{
if(k==1)
{
d[k][x1][y1][x2][y2]=s(x1,y1,x2,y2);
return d[k][x1][y1][x2][y2];
}
if(d[k][x1][y1][x2][y2]) return d[k][x1][y1][x2][y2];
double t1=100000000,t2=100000000;
for(int a=x1;a<x2;a++)
{
t1=min(t1,min(dfs(k-1,x1,y1,a,y2)+s(a+1,y1,x2,y2),dfs(k-1,a+1,y1,x2,y2)+s(x1,y1,a,y2)));
}
for(int b=y1;b<y2;b++)
{
t2=min(t2,min(dfs(k-1,x1,y1,x2,b)+s(x1,b+1,x2,y2),dfs(k-1,x1,b+1,x2,y2)+s(x1,y1,x2,b)));
}
d[k][x1][y1][x2][y2]=min(t1,t2);
return d[k][x1][y1][x2][y2];
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
memset(sum,0,sizeof(sum));
memset(d,0,sizeof(d));
for(int i=1;i<=8;i++)
for(int j=1;j<=8;j++)
{
scanf("%lf",&a[i][j]);
sum[i][j]=a[i][j]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
}
ave=sum[8][8]/n;
dfs(n,1,1,8,8);
printf("%.3f\n",sqrt(d[n][1][1][8][8]/n-ave*ave));
}
return 0;
}
分享到:
相关推荐
1.把自己的污水排到河里V 2.把自己的污水送到右边> 3.把自己的污水送到左边
这是一道很不错的题目,dp解决的经典例子,是学习dp,和练习的好题目。。。。
北大POJ3009-Curling 2.0【DFS+Vector+回溯+剪枝】 解题报告+AC代码
北大POJ3026-Borg Maze【BFS+Prim】 解题报告+AC代码
北大POJ初级-所有题目AC代码+解题报告
北大POJ3733-Changing Digits【DFS+强剪枝】 解题报告+AC代码
北大POJ3373-Changing Digits【DFS+强剪枝】 解题报告+AC代码
POJ2186-Popular Cows 【Tarjan+极大强连通分量+缩点】 解题报告+AC代码 http://hi.csdn.net/!s/BGDH68 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
POJ1321棋盘问题 很好两种解法很值得去参考一下 完整的实验报告还有代码希望kan
坐标型动态规划 poj1191棋盘分割 poj1088滑雪 noi过河卒 动态规划的解题思想及思路
poj1085,记忆化DP+状态压缩求解
关于poj dp分类,我一直寻找dp的分类,终于找到了,也上传一下
北大POJ初级-简单搜索 解题报告+AC代码
北大POJ初级题-数据结构:解题报告+AC代码
北大POJ2187-Beauty Contest 解题报告+AC代码
博客链接 http://blog.csdn.net/CABI_ZGX/article/details/52701138
北大POJ3252-Round Numbers 解题报告+AC代码
北大POJ1416-Shredding Company 解题报告+AC代码
Poj 3342 这是一道树状dp题目,题意是这样的,一个公司,每个人有且仅有一个Boss,除了最大的Boss没有Boss(显然),现在要参加一个聚会,要求参加的人数最多,但是棘手的.......
北大POJ1019-Number Sequence 解题报告+AC代码