poj-1191-棋盘分割_齐豪的博客-程序员秘密

技术标签： 模拟/枚举  

题目地址

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

题目大意

这里写图片描述
这里写图片描述

解题思路

这里写图片描述
这里写图片描述
这里写图片描述

Code


#include <stdio.h>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <map>
#include <vector>
#include <math.h>
#include <algorithm>
#define INF 0x3fffffff
#define N 80

using namespace std;
typedef long long LL;

int n;
int s[9][9]; //每个格子的分数
int sum[9][9]; //(1,1)到(i,j)的矩形的分数之和
int res[15][9][9][9][9]; //fun的记录表

//(x1,y1)到(x2,y2)的矩形的分数之和
int get_sum(int x1, int y1, int x2, int y2) {
    return sum[x2][y2] - sum[x2][y1-1] - sum[x1-1][y2] + sum[x1-1][y1-1];
}

int fun(int n, int x1, int y1, int x2, int y2) {
    if (res[n][x1][y1][x2][y2] != -1) {
        return res[n][x1][y1][x2][y2];
    }
    if (n == 1) {
        int ans = get_sum(x1, y1, x2, y2);
        res[n][x1][y1][x2][y2] = ans*ans;
        return res[n][x1][y1][x2][y2];
    }
    int MIN = INF;
    for (int x = x1; x < x2; x++) {
        int up = get_sum(x1, y1, x, y2);
        int down = get_sum(x+1, y1, x2, y2);
        int local = min(fun(n-1, x1, y1, x, y2) + down*down, fun(n-1, x+1, y1, x2, y2) + up*up);
        MIN = min(MIN, local);
    }
    for (int y = y1; y < y2; y++) {
        int left = get_sum(x1, y1, x2, y);
        int right = get_sum(x1, y+1, x2, y2);
        int local = min(fun(n-1, x1, y1, x2, y) + right*right, fun(n-1, x1, y+1, x2, y2) + left*left);
        MIN = min(MIN, local);
    }
    res[n][x1][y1][x2][y2] = MIN;
    return MIN;
}

int main() {

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#else
    //
#endif
    scanf("%d", &n);
    memset(sum, 0, sizeof(sum));
    memset(res, -1, sizeof(res));
    for (int i = 1; i < 9; i++) {
        int row_sum = 0;
        for (int j = 1; j < 9; j++) {
            scanf("%d", &s[i][j]);
            row_sum += s[i][j];
            sum[i][j] = sum[i-1][j] + row_sum;
        }
    }
    double ans = fun(n, 1, 1, 8, 8) - 1.0 * (sum[8][8]*sum[8][8]) / n;
    ans = sqrt(ans/n);
    printf("%.3f\n", ans);
    return 0;
}

参考

https://d396qusza40orc.cloudfront.net/pkupop/lectures/Week12/W12-03_%E9%80%92%E5%BD%92-%E6%A3%8B%E7%9B%98%E5%88%86%E5%89%B2.pdf
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/qq_33096883/article/details/77500662

智能推荐

虚拟机ubuntu使用串口_weixin_30348519的博客-程序员秘密

1. 电脑的串口默认是在windows系统上，需要把串口转到ubuntu上面，按照下面的步骤先2. 找到需要使用的串口3. 在VMWARE里面连接该串口或者使用方法4. 成功之后，检查一下ls /dev/tty*，最后两个就是映射出来的串口转载于:https://www.cnblogs.com/429512065qhq/p/9401286.html...

试验设计第二版茆诗松课后题答案_茆诗松数理统计学答案_三十六陂的博客-程序员秘密

茆诗松数理统计学答案【篇一：数理统计】txt&gt;mathematicalstatistics课程代码：课程性质：专业基础理论课适用专业：统计开课学期：4总学时数：56总学分数：3.5编写年月：2007.5修订年月：2007.7执笔：邱红兵一、课程的性质和目的?本课程以概率论为基础开设本课程的目的在于通过教与学，使学生掌握数理统计的基本思想、基本理论和一般方法，具有一定的解决随机现象的实际问题...

hive 中 json 字符串解析之 get_json_object 与 json_tuple_get_jason_冰阔落的博客-程序员秘密

    在技术对app进行埋点时，会讲多个字段存放在一个数组中，因此模型调用数据时，要对埋点数据进行解析，以作进一步的清洗。本文将介绍解析json字符串的两个函数：get_json_object和json_tuple。表结构如下：一、get_json_object函数的作用：用来解析json字符串的一个字段：select get_json_object(flist,'$.fi...

Hibernate_入门_小张同学_java的博客-程序员秘密

目录一、概念二、主键生成策略①程序员自己控制：assigned② 数据库控制: identity(标识列/自动增长) sequence③ hibernate控制:increment uuid/uuid.hex④ 其它:native三、使用①在pom.xml中导入Hibernate相关依赖②配置hibernate.cfg.xml文件③创建实体类，配置映射文件④测试一、概念Hibernate是持久层的ORM框架，我们可以通过操作java对象来操作我们的数据库数

根据给定日期判断当天是星期几_Waiting的博客-程序员秘密

根据日期判断当前是星期几

二叉查找树(BST)_(bst-lchild,x)_大脸猫Coding的博客-程序员秘密

title: 二叉查找树(BST)date: 2020-01-13 20:36:30tags: 数据结构1.1二叉查找树定义二叉查找树（Binary Search Tree, BST）是特殊的二叉树，又称排序二叉树、二叉搜索树、二叉排序树。递归定义：①可为一棵空树②非空则由根结点、左子树、右子树组成。左右子树均为一棵二叉查找树，且根结点、根左孩子、根右孩子大小为 左孩子&lt;=根...

随便推点

浪潮财务软件遇到问题_ ╃姃恠輸扖中...╃的博客-程序员秘密

一、系统公共1、安装软件，安装到配置注册信息的时候提示failed to set data for。。需要关闭360安全卫士以后再安装软件2、网络锁授权介绍2.1、8.5之前的版本（包括8.5）、9.0、9.1这些版本是分单机锁与网络锁的，单机锁的锁号是以MH开头的；网络锁的锁号是以NH开头。2.2、8.5.1和10.X的版本，统一改为单机锁，通过License文件来记录单机还是网络信息...

Jdk1.7 与 jdk1.8的区别，最新的特征有哪些(美团，360，京东面试题目)_diaopai5230的博客-程序员秘密

在jdk7的新特性方面主要有下面几方面的增强：1.1二进制变量的表示,支持将整数类型用二进制来表示，用0b开头。 所有整数int、short、long、byte都可以用二进制表示：byte aByte = (byte) 0b00100001;延伸阅读：java的8种基础类型一、基础类型Java 是一种强类型语言 。 这就意味着必须为每一...

CSR867x — 蓝牙音频发射器方案（支持USB、模拟和SPDIF）_文化人Sugar的博客-程序员秘密

写在前面：使用BC5和CSR8670的芯片，分别实现蓝牙音频发射器方案；1、选择ADK的source工程编译下载，然后参考对应的source用户手册（BC57E687C和CSR8670）；2、注意USB模式时，硬件上要把BC5：VDD_USB CSR8670：VBUS_CHG_5V脚接高；3、通过用户手册可以看到BC5支持USB和analogue两种模式,而CSR8670支持USB，analogue和SPDIF（TOSLINK光纤）三种工作模式，如下：

Redis专题详细教程（二）_浩哥要努力的博客-程序员秘密

Redis持久化：RDB触发机制：1.save的规则满足的情况下，会自动触发rdb规则2.执行flushall命令，也会触发rdb规则3.退出redis，也会产生rdb文件备份就会自动生成一个rdb文件dump.rdb恢复rdb文件，只需要将dump.rdb文件放到redis 的启动目录（config get dir命令查看，一般为/usr/local/bin）下就行了，redis启动时会自动检查dump.rdb恢复其中的数据优点：1.适合大规模的数据恢复2.对数据的完整星要求不高

WebRTC音频接收处理全过程（二）_webrtc remote-audio_爱技术爱生活的博客-程序员秘密

webrtc拿到订阅远端数据的answer后，设置远端sdp，启动音频渲染线程，循环向neteq的数据包接受队列中拿音频包解码输出webrtc_d.dll!webrtc::AudioDeviceWindowsCore::DoRenderThread() 行2975 C++ 启动渲染进程，取数据包解码后进行渲染webrtc_d.dll!webrtc::AudioDeviceWindowsCore::WSAPIRenderThread(void * context) 行2778 C++w...

hbuilder预览无法使用的解决办法_hbuilderx预览不出来怎么弄_night 猿的博客-程序员秘密

hbuilder预览无法使用预览的插件下载不了多半是杀毒软件（例如手机管家，火绒等等）没关闭，把他关闭之后还下载不了的话，就重启计算机，当然杀毒软件不能打开。下载了内置浏览器之后，预览点了之后没反应。你需要找到hbuilder的安装位置，在那里会有一个bin文件夹，把bin文件夹里的内容复制到和hbuilder.exe的同级目录下，就可以了。...

推荐文章

热门文章

相关标签