标准差=√(Σ(xi-xba)2/n)=Σ(xi)2+xba*n-2*xba*sum。只需最小化每个分割出来的矩阵的平方和即可。

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
#define INF 2000000000
typedef double db;
int mem[11][11][11][11][11],a[11][11],pre[11][11],m,n,K;
int sum;
db xba;
int sqr(int x){return x*x;}
int calc(int x1,int y1,int x2,int y2)
{return pre[x2][y2]-pre[x1-1][y2]-pre[x2][y1-1]+pre[x1-1][y1-1];}
int f(int x1,int y1,int x2,int y2,int K)
{
if(mem[x1][y1][x2][y2][K]<INF) return mem[x1][y1][x2][y2][K];
if(K==1) return mem[x1][y1][x2][y2][K]=sqr(calc(x1,y1,x2,y2));
for(int i=x1;i<x2;++i)
for(int j=1;j<K;++j)
if((y2-y1+1)*(i-x1+1)>=j&&(y2-y1+1)*(x2-i)>=K-j)
mem[x1][y1][x2][y2][K]=min(mem[x1][y1][x2][y2][K],f(x1,y1,i,y2,j)+f(i+1,y1,x2,y2,K-j));
for(int i=y1;i<y2;++i)
for(int j=1;j<K;++j)
if((x2-x1+1)*(i-y1+1)>=j&&(x2-x1+1)*(y2-i)>=K-j)
mem[x1][y1][x2][y2][K]=min(mem[x1][y1][x2][y2][K],f(x1,y1,x2,i,j)+f(x1,i+1,x2,y2,K-j));
return mem[x1][y1][x2][y2][K];
}
int main()
{
scanf("%d%d%d",&n,&m,&K);
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
{
scanf("%d",&a[i][j]);
sum+=a[i][j];
pre[i][j]=pre[i][j-1]+a[i][j];
}
xba=(db)sum/(db)K;
for(int j=1;j<=m;++j)
for(int i=1;i<=n;++i)
pre[i][j]+=pre[i-1][j];
memset(mem,0x7f,sizeof(mem));
printf("%.2f\n",sqrt(((db)f(1,1,n,m,K)+(db)K*xba*xba-2.0*(db)sum*xba)/(db)K));
return 0;
}

最新文章

  1. 渗透测试报告收集、生成工具MagicTree
  2. 最详细eclipse汉化插件安装教程
  3. 用Wireshark抓包分析超过70秒的请求
  4. NOIP 2001解题报告
  5. 【Qt】Qt之Tab键切换焦点顺序【转】
  6. 1470. UFOs(三维树状数组)
  7. PHP程序缓存之文件缓存处理方式
  8. .Net下的MSMQ(微软消息队列)的同步异步调用
  9. 把AS代码链接到fla文件
  10. 企业架构研究总结(39)——TOGAF架构能力框架之架构委员会和架构合规性
  11. OPENWRT make defconfig错误之一
  12. 二叉树,平衡树,红黑树,B~/B+树汇总
  13. jdbc批量执行SQL insert 操作
  14. Chipmunk僵尸物理对象的出现和解决(二)
  15. GWAS: 阿尔兹海默症和代谢指标在大规模全基因组数据的遗传共享研究
  16. 爬虫---爬虫er与反爬虫er之间的斗争 转发
  17. PL/SQL Developer如何导出数据成sql的insert语句
  18. 2018年 js 简易控制滚动条滚动的简单方法
  19. spring自带测试配置
  20. IO流_文件切割与合并(带配置信息)

热门文章

  1. JSON各种转换总结
  2. 动态规划:状压DP-斯坦纳树
  3. MyBatis系列三 之 使用getMapper剔除掉Dao的实现类
  4. python imageai 对象检测、对象识别
  5. 前端开发各种cross之cross domain
  6. elementary os 5配置
  7. centos7.3安装caffe出现错误:/bin/ld: cannot find -lcblas /bin/ld: cannot find -latlas
  8. JDK 动态代理 源码简单分析
  9. Selenium2+python自动化56-unittest之断言(assert)【转载】
  10. hdu4240 求一条流量最大的路/(此题网上百分之90以上算法是错误的)