poj-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

本文链接：https://blog.csdn.net/qq_33096883/article/details/77500662

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

查找算法练习题_关于二分查找算法在下面的有序表中 ( 15, 24, 32, 47, 50, 58, 62, 79_chf_1的博客-程序员秘密

1、在对有二十个数据有序表作二分查找时有___________个结点的查找长度是4.2、用折半查找法的查找速度比用顺序查找法的查找速度_________. A 必然慢 B必然快 C速度相等 D 快慢不定3、写出从循环单链表中查找出最大值的算法.4、写出从循环单链表中查找出最小值的算法 .5、适合折半查找的表的存贮方式及元素排列要求为( ) A、链...

Java2D——仿Windows7扫雷_kakashi8841的博客-程序员秘密

先看下效果图吧：运行程序、源码、资源图片下载地址：（文件还在审核中...审核后将加入下载地址）

用WinRAR进行安装包的制作_angou6476的博客-程序员秘密

简单的绿色的安装包制作工具，如果不想用复杂且庞大的vs提供的制作工具，或许这个绿色解压安装包是个不错的选择。下面我收集了一些制作的教程（百度经验的文章）和一些常用到的命令行：WinRAR自解压安装包制作步骤：1、先选中要创建自解压文件的多个文件或文件夹，并单击右键，从弹出菜单中选择“添加到压缩文件”命令：2、在弹出的框中，切换到“常规”选项卡下，并选择“创...

Aert_Log: 设计一个精简易用的日志_bj123nimab的博客-程序员秘密

日志记录对于应用的维护特别是对于已部署到运行环境之后的应用调试都有着重要的意义。对于一个应用的日志系统而言，首先必须得有一个日志对象，该对象负责记录日志信息。同时该信息可以输出到不同的位置，例如控制台，文件甚至网络中。对于信息的格式，则可以根据不同的需求，可以输出成普通文本，XML 或者 HTML 的格式。同时还需要对日志信息进行不同级别的分类，这样的好处是可以过滤冗余信息，只保留关...

NFS-Client-Provisioner与SC使用_provisioner sc 怎么定义_孤烟。的博客-程序员秘密

1. NFS-Client-Provisioner1.1 下载NFS-Client-Provisioner文件$ wget -c https://codeload.github.com/kubernetes-retired/external-storage/zip/refs/heads/master$ unzip master# # 所有的部署文件均在deploy目录中$ cd /root/external-storage-master/nfs-client/deploy/1.2 创建授权

irrlicht引擎消息系统_irrlicht消息_gauss的博客-程序员秘密

说说irrlicht的消息系统，除了irrlicht绘制主窗体，默认的消息处理过程，外部的消息监听是通过IrrlichtDevice设备类中一个接口virtual void setEventReceiver(IEventReceiver* receiver) = 0;这个接口是把receiver监听类作物除默认窗体过程外，消息传递对象，先看看看IEventReceiver接口里面有什么

随便推点

通过SCCM给受限用户卸载软件的权限_weixin_33924770的博客-程序员秘密

HI 大家好，我是Cantgis，我现在要解决的是给大家卸载软件的权限。当SCCM代理客户端安装到用户计算机的时候，但很多时候由于软件错误，需要进行卸载重新安装，远程协助用户桌面时，也只能通过按住"Shift"键后，右键以管理员身份执行“添加和删除程序”当域中计算机的本地管理员密码没有被更新成网管的统一密码时，不能提升该卸载的权限，同时一些卸载的操...

python splinter api整理_csdn_meng的博客-程序员秘密

官方文档：Splinter — Splinter 0.10.0 documentationfrom splinter import Browser # 导入包browser = Browser() # 创建一个实例# if you don’t provide any driver to the Browser function, firefox will be used# 如果没有...

ffmpeg 调整相片大小,如何使用ffmpeg的sws_scale（）调整图片大小？_熊江乔的博客-程序员秘密

I wanna resize a picture by using the ffmpeg's func--->sws_scale().Is there any one knows how to do it?Do you have the source code for this function?解决方案First you need to create a SwsContext (you n...

控制QLineEdit的输入范围_hedtao的博客-程序员秘密

控制QLineEdit的输入范围1.使用正则表达式检验QLineEdit的输入范围(代码如下):#include #include QLineEdit *lineEdit = new QLineEdit(this);QRegExp regExp("[A-Za-z][1-9][0-9]{0,2}"); //^[1-9][0-9]*$ 和 ^[1-9]{1}[/d]*

治愈、连接、多元化，探探成年轻人精神“归属地”_京比特的博客-程序员秘密

探探正成为年轻人们的精神归属地。8月12日，南方都市报联合社交平台探探发布了《2020独居青年生活洞察报告》。一、《2020独居青年生活洞察报告》回顾互联网世代的年轻人群体，对“独居”这种状态持什么态度？在独居生活中，他们又是如何处理自己的心理、情感问题和社交需求？这就是《2020独居青年生活洞察报告》（以下称《报告》）所关注的核心问题。据了解，探探与南方都市报此次联合调查对象主要为探探平台年龄段介于18至35岁之间的用户群体。本次调查对象中高达91.83%的比例均为未婚单身者。数据显示，其

【计算机系统结构】指令级并行_柔水终成雕刀╮(￣▽￣"")╭的博客-程序员秘密

赶在最后一天再更一点吧，生死时速文章目录指令级并行概念基本块BB相关与冲突数据相关名相关控制相关循环展开概念注意点：限制动态分支预测采用分支历史表BHTCorrelated Branch PredictionTournament(竞赛) Predictors采用目标缓冲器Branch Target Buffers (BTB)小结动态调度记分牌算法Tomasulo算法前瞻执行Speculation关键思想：reorder buffer (ROB) 再定序缓冲Tomasulo with ReOrder..