【记忆化搜索】bzoj1048 [HAOI2007]分割矩阵
2024-10-22 05:11:54
标准差=√(Σ(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;
}
最新文章
- 渗透测试报告收集、生成工具MagicTree
- 最详细eclipse汉化插件安装教程
- 用Wireshark抓包分析超过70秒的请求
- NOIP 2001解题报告
- 【Qt】Qt之Tab键切换焦点顺序【转】
- 1470. UFOs(三维树状数组)
- PHP程序缓存之文件缓存处理方式
- .Net下的MSMQ(微软消息队列)的同步异步调用
- 把AS代码链接到fla文件
- 企业架构研究总结(39)——TOGAF架构能力框架之架构委员会和架构合规性
- OPENWRT make defconfig错误之一
- 二叉树,平衡树,红黑树,B~/B+树汇总
- jdbc批量执行SQL insert 操作
- Chipmunk僵尸物理对象的出现和解决(二)
- GWAS: 阿尔兹海默症和代谢指标在大规模全基因组数据的遗传共享研究
- 爬虫---爬虫er与反爬虫er之间的斗争 转发
- PL/SQL Developer如何导出数据成sql的insert语句
- 2018年 js 简易控制滚动条滚动的简单方法
- spring自带测试配置
- IO流_文件切割与合并(带配置信息)
热门文章
- JSON各种转换总结
- 动态规划:状压DP-斯坦纳树
- MyBatis系列三 之 使用getMapper剔除掉Dao的实现类
- python imageai 对象检测、对象识别
- 前端开发各种cross之cross domain
- elementary os 5配置
- centos7.3安装caffe出现错误:/bin/ld: cannot find -lcblas /bin/ld: cannot find -latlas
- JDK 动态代理 源码简单分析
- Selenium2+python自动化56-unittest之断言(assert)【转载】
- hdu4240 求一条流量最大的路/(此题网上百分之90以上算法是错误的)