http://poj.org/problem?id=1191

题意:中文题。

题解:

1.关于切割的模拟,用递归 有这样的递归方程(dp方程):f(n,棋盘)=f(n-1,待割的棋盘)+f(1,割下的棋盘)

2.考虑如何计算方差,根据以下方差公式

我们只需算∑X 2的最小值//然后将它乘以n,减去总和的平方,除以n^2,再整体开根号就行了,化简一下的结果

3.关于棋盘的表示,我们用左上角坐标与右下角坐标,常规表示

4.关于计算优化,用sum二维前缀和。并且进行记忆化递归。

技巧:1&引用 化简代码 2 二维前缀和的预处理

坑:我在poj上搜找这题,搜chess,rectangle,cut死活找不到,组后发现是到noi的中文题qrz。。。

  +1,-1 要注意

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <math.h>
#include <string.h>
#include <string>
#include <map>
#include<stack>
#include<set>
#include<string.h>
#include<iomanip>
#define pb push_back
#define _for(i, a, b) for (int i = (a); i<(b); ++i)
#define _rep(i, a, b) for (int i = (a); i <= (b); ++i) using namespace std;
const int N =+ ;
//double num[N], price[N], ave[N];
int s[N][N];
int sum[N][N];
int res[][N][N][N][N];
int calSum(int x1, int y1, int x2, int y2) {
return sum[x2][y2] - sum[x2][y1-] - sum[x1-][y2] + sum[x1-][y1-];
}
int f(int n, int x1, int y1, int x2, int y2) {
int t, a, b, c, e, mn = 1e7;
int& ans = res[n][x1][y1][x2][y2];
if (ans != -) return ans;
if (n == ) {
t = calSum(x1, y1, x2, y2);
ans = t*t;
return ans;
}
for (a = x1; a < x2; a++) {
c = calSum(a + , y1, x2, y2);
e = calSum(x1, y1, a, y2);
t = min(c*c + f(n - , x1, y1, a, y2), e*e + f(n-,a + , y1, x2, y2));
if (mn > t)mn = t;
}
for (b = y1; b < y2; b++) {
c = calSum(x1, b+, x2, y2);
e = calSum(x1, y1, x2, b);
t = min(c*c + f(n-,x1, y1, x2, b), e*e + f(n-,x1, b + , x2, y2));
if (mn > t)mn = t;
}
ans = mn;
return ans;
}
int main() {
memset(res, -, sizeof(res));
int n;
cin >> n; _for(i,,)
for(int j=,rowsum=;j<;j++) {
cin >> s[i][j];
rowsum += s[i][j];
sum[i][j] += sum[i - ][j] + rowsum;
} double result = n*f(n, , , , ) - sum[][] * sum[][];
cout << setiosflags(ios::fixed) << setprecision() << sqrt(result / (n*n)) << endl; system("pause");
}

最新文章

  1. cacti 安装
  2. js 控制 css3高级运动 keyframes
  3. CentOS 6.3下配置LVM(逻辑卷管理)
  4. [CF225C] Barcode (简单DAG上dp)
  5. 碎片事物的提交 commitAllowingStateLoss()
  6. 初识jQuery 2013-09-26
  7. windows下跑python flask,环境配置
  8. what are Datatypes in SQLite supporting android
  9. ICallbackEventHandler 接口实现回调处理功能
  10. JAVA 面试整理,面试汇总
  11. Linux 下通过脚本实现远程自动备份
  12. android 读取txt文件内容
  13. java基础-修饰符
  14. react的初涉入
  15. [转]为什么大型网站前端使用 PHP 后台逻辑用 Java?
  16. windows7.0旗舰版安装后控制面板自带的Microsoft程序
  17. MySQL EXTRACT() 函数
  18. Android开发:修改eclipse里的Android虚拟机路径
  19. Redis进阶学习笔记
  20. Java的selenium代码随笔(2)

热门文章

  1. 01-虚拟软件vmware安装
  2. 5 -- Hibernate的基本用法 --1 3 流行的ORM框架简介
  3. WinForm中实现HotKey
  4. Git Step by Step – (1) Git 简介
  5. 利用Visio绘制数据流图与组织结构图
  6. RFC文件
  7. Linux应急响应(四):盖茨木马
  8. python框架----&gt;BeautifulSoup的使用
  9. shell 获取脚本的绝对路径
  10. 【大数据系列】hadoop核心组件-MapReduce