C++---区间DP---棋盘分割(每日一道算法2023.5.2)

这篇具有很好参考价值的文章主要介绍了C++---区间DP---棋盘分割(每日一道算法2023.5.2)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

注意事项:
涉及到"矩阵/二维前缀和"的一些知识,建议先理解那篇文章。

题目:
将一个 8×8 的棋盘进行如下分割:将原棋盘割下一块矩形棋盘并使剩下部分也是矩形,再将剩下的部分继续如此分割,这样割了 (n−1) 次后,连同最后剩下的矩形棋盘共有 n 块矩形棋盘。(每次切割都只能沿着棋盘格子的边进行)
C++---区间DP---棋盘分割(每日一道算法2023.5.2)

原棋盘上每一格有一个分值,一块矩形棋盘的总分为其所含各格分值之和。
现在需要把棋盘按上述规则分割成 n 块矩形棋盘,并使各矩形棋盘总分的均方差最小。

均方差 C++---区间DP---棋盘分割(每日一道算法2023.5.2),其中平均值 C++---区间DP---棋盘分割(每日一道算法2023.5.2),xi 为第 i 块矩形棋盘的总分。

请编程对给出的棋盘及 n,求出均方差的最小值。

输入格式
第 1 行为一个整数 n。
第 2 行至第 9 行每行为 8 个小于 100 的非负整数,表示棋盘上相应格子的分值。每行相邻两数之间用一个空格分隔。

输出格式
输出最小均方差值(四舍五入精确到小数点后三位)。

数据范围
1<n<15

输入:
3
1 1 1 1 1 1 1 3
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0
1 1 1 1 1 1 0 3
输出:
1.633
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 15, M = 9, INF = 1e9;
int n, m = 8;                   //n为最多分割的次数,m固定为棋盘的长宽8*8
int s[M][M];                    //s数组是棋盘的二维前缀和,用来快捷的求出一个区域内的值的总和
double f[M][M][M][M][N];        //f[x1][y1][x2][y2][k]
double X;                       //大写X表示均方差公式中的X拔

double get(int x1, int y1, int x2, int y2) {        //得到(x1, y1)为左上点,(x2, y2)为右下点的区间内的值
    double sum = (s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1]) - X;
    return sum*sum / n;
}

double dp(int x1, int y1, int x2, int y2, int k) {  //区间dp
    double &v = f[x1][y1][x2][y2][k];
    if (v >= 0) return v;                       //记忆化搜索,如果当前区间已被计算,直接返回值即可
    if (k == 1) return get(x1, y1, x2, y2);     //如果当前k为1说明是最后一刀,那么就直接返回(x1, y1)(x2, y2)这个区间内的值即可

    //v设为正无穷,因为要取min
    v = INF;
    for (int i = x1; i<x2; i++) {   //枚举x1到x2之间的每一个分割线
        v = min(v, dp(x1, y1, i, y2, k-1) + get(i+1, y1, x2, y2));
        v = min(v, dp(i+1, y1, x2, y2, k-1) + get(x1, y1, i, y2));
    }
    for (int i = y1; i<y2; i++) {   //枚举y1到y2之间的每一个分割线
        v = min(v, dp(x1, y1, x2, i, k-1) + get(x1, i+1, x2, y2));
        v = min(v, dp(x1, i+1, x2, y2, k-1) + get(x1, y1, x2, i));
    }
    return v;
}

int main() {
    //读入,处理二维前缀和
    cin >> n;
    for (int i = 1; i<=m; i++) {
        for (int j = 1; j<=m; j++) {
            cin >> s[i][j];
            s[i][j] = s[i][j] + s[i-1][j] + s[i][j-1] - s[i-1][j-1];
        }
    }

    //f初始化为负数
    memset(f, -1, sizeof f);
    X = (double)s[m][m] / n;
    
    //输出小数点3位,并把算出的最小值开方
    printf("%.3lf", sqrt(dp(1, 1, 8, 8, n)));
    return 0;
}

思路:
思路很简单,其实就是枚举棋盘的所有分割方式,
具体为每次对棋盘进行一次横切或竖切,将棋盘分成两块矩形的子棋盘,
分割完一次后,我们可以选择两个子棋盘中的一个再继续递归操作,
直到分割次数k用完或已经不能再切割为止。

还是经典的y式dp分析法
1.状态表示
f[x1][y1][x2][y2][k]:
以(x1, y1)为左上角,(x2, y2)为右下角的区域,分割k次的所有方案,
属性为Min(最小均方差)。

2.状态计算
枚举所有当前选取的区间的切分可能性:

1.横切,y1y2间的所有分界线k(切y轴)
上区间值:top = value(x1, y1, x2, k)
下区间值:bot = value(x1, k+1, x2, y2)

2.竖切,x1x2间的所有分界线k(切x轴)
左区间值:left = value(x1, y1, k, y2)
右区间值:right = value(k+1, y1, x2, y2)

注意这里横切和竖切是并列的关系而不是嵌套,因为横切了就不能竖切,竖切了就不能横切,只能取一种,Min(top, bot, left, right) 即为当前区间最小均方差。

如果有所帮助请给个免费的赞吧~有人看才是支撑我写下去的动力!

声明:
算法思路来源为y总,详细请见https://www.acwing.com/
本文仅用作学习记录和交流文章来源地址https://www.toymoban.com/news/detail-434724.html

到了这里,关于C++---区间DP---棋盘分割(每日一道算法2023.5.2)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • C++---背包模型---潜水员(每日一道算法2023.3.13)

    注意事项: 本题是\\\"动态规划—01背包\\\"和\\\"背包模型—二维费用的背包问题\\\"的扩展题,优化思路不多赘述,dp思路会稍有不同,下面详细讲解。 题目: 潜水员为了潜水要使用特殊的装备。 他有一个带2种气体的气缸:一个为氧气,一个为氮气。 让潜水员下潜的深度需要各种数

    2024年02月09日
    浏览(35)
  • C++---最长上升子序列模型---最大上升子序列和(每日一道算法2023.3.3)

    注意事项: 本题为\\\"线性dp—最长上升子序列的长度\\\"的扩展题,所以dp思路这里就不再赘述。 题目: 比如,对于序列(1,7,3,5,9,4,8),有它的一些上升子序列,如(1,7),(3,4,8)等。 这些子序列中和最大为18,为子序列(1,3,5,9)的和。 你的任务,就是对于给定的序列,求出最大上升子序

    2024年02月03日
    浏览(36)
  • acwing算法基础之动态规划--线性DP和区间DP

    线性DP:状态转移表达式存在明显的线性关系。 区间DP:与顺序有关,状态与区间有关。 题目1 :数字三角形。 解题思路:直接DP即可, f[i][j] 可以来自 f[i-1][j] + a[i][j] 和 f[i-1][j-1] + a[i][j] ,注意 f[i-1][j] 不存在的情况(最后一个点)和 f[i-1][j-1] 不存在的情况(第一个点)。

    2024年02月04日
    浏览(49)
  • 【LeetCode每日一题: 1039. 多边形三角剖分的最低得分 | 暴力递归=>记忆化搜索=>动态规划 | 区间dp 】

    🍎作者简介:硕风和炜,CSDN-Java领域新星创作者🏆,保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享💎💎💎 🍎座右铭:人生如棋,我愿为卒,行动虽慢,可谁曾见我后退一步?🎯🎯🎯 1039. 多边形三角剖分的最

    2023年04月19日
    浏览(52)
  • 每日一道算法题 1

    借鉴文章:Java-敏感字段加密 - 哔哩哔哩 题目描述  给定一个由多个命令字组成的命令字符串; 1、字符串长度小于等于127字节,只包含大小写字母,数字,下划线和偶数个双引号 2、命令字之间以一个或多个下划线_进行分割 3、可以通过两个双引号\\\"\\\"来标识包含下划线_的命令

    2024年02月04日
    浏览(35)
  • 算法基础复盘笔记Day11【动态规划】—— 区间DP、计数类DP、树形DP、记忆化搜索

    ❤ 作者主页:欢迎来到我的技术博客😎 ❀ 个人介绍:大家好,本人热衷于 Java后端开发 ,欢迎来交流学习哦!( ̄▽ ̄)~* 🍊 如果文章对您有帮助,记得 关注 、 点赞 、 收藏 、 评论 ⭐️⭐️⭐️ 📣 您的支持将是我创作的动力,让我们一起加油进步吧!!!🎉🎉 1. 题目

    2024年02月01日
    浏览(40)
  • 【力扣每日一题】2023.8.28 插入区间

    目录 题目: 示例: 分析: 代码: 和昨天的题大差不差,我们仍然是有一堆区间,题目给我们一个新的区间,要我们把新区间插入到原本的区间数组里,并且能合并的要合并。 我们可以直接把新区间放入数组里,接着执行昨天的代码即可,一行都不用改,甚至形参名字都是

    2024年02月10日
    浏览(43)
  • 【力扣每日一题】2023.8.27 合并区间

    目录 题目: 示例: 分析: 代码: 那么合并区间是在什么情况下才能合并呢? 我总结为两种情况 第一种情况就是这样,第二个区间的左区间大于第一个区间的左区间但是小于第一个区间的右区间,并且第一个区间的右区间小于第二个区间的右区间,这种情况下合并的结果就

    2024年02月11日
    浏览(34)
  • 2023-08-28 LeetCode每日一题(插入区间)

    点击跳转到题目位置 给你一个 无重叠的 ,按照区间起始端点排序的区间列表。 在列表中插入一个新的区间,你需要确保列表中的区间仍然有序且不重叠(如果有必要的话,可以合并区间)。 示例 1: 示例 2: 示例 3: 示例 4: 示例 5: 提示: 0 = intervals.length = 10 4 interval

    2024年02月11日
    浏览(46)
  • 2023-08-27 LeetCode每日一题(合并区间)

    点击跳转到题目位置 以数组 intervals 表示若干个区间的集合,其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间,并返回 一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间 。 示例 1: 示例 2: 提示: 1 = intervals.length = 10 4 intervals[i].length == 2 0 = s

    2024年02月10日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包