动态规划—区间DP(一)

简介: AcWing算法提高课内容,本文讲解 动态规划

前言

AcWing算法提高课内容,本文讲解 动态规划

本篇包括以下题目:

⭐️ AcWing 1068. 环形石子合并

⭐️ AcWing 320. 能量项链

⭐️ AcWing 479. 加分二叉树

⭐️ AcWing 1069. 凸多边形的划分


写博客有哪里不完善的地方或者有哪里表达错误希望大家提出来,博主会立即改正!望大家海涵


本文需要先自修基础:区间DP


环形石子合并

题目要求

题目描述:

image.png

输入格式:

第一行包含整数 n ,表示共有 n  堆石子。

第二行包含 n 个整数,分别表示每堆石子的数量。

输出格式:

输出共两行:

第一行为合并得分总和最小值,

第二行为合并得分总和最大值。

数据范围:

1≤n≤200

输入样例:

4
4 5 9 4

输出样例:

43
54

思路分析

环形的问题我们都可以变环为线,即我们开两倍的大小,然后以n为长度进行枚举即可,下面给一个示例图:

image.png

这样,我们直接对展开的直线以长度为 6 进行遍历,和直接枚举一个环的效果是一致的,为了更快的求出一段区间的和,可以使用前缀和的思维进行优化,前缀和讲解见博客:前缀和算法

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 410;
int f[N][N], g[N][N];
int w[N], s[N];
int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> w[i], w[i + n] = w[i];
    for (int i = 1; i <= 2 * n; i ++ ) s[i] = s[i - 1] + w[i];
    memset(g, 0x3f, sizeof g);
    for (int i = 1; i <= 2 * n; i ++ ) g[i][i] = 0;
    for (int len = 2; len <= n; len ++ )
        for (int l = 1; l + len - 1 <= 2 * n; l ++ )
        {
            int r = l + len - 1;
            for (int k = l; k < r; k ++ )
            {
                f[l][r] = max(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
                g[l][r] = min(g[l][r], g[l][k] + g[k + 1][r] + s[r] - s[l - 1]);   
            }
        }
    int maxv = 0, minv = 0x3f3f3f3f;    
    for (int i = 1; i <= n; i ++ )
    {
        maxv = max(maxv, f[i][i + n - 1]);
        minv = min(minv, g[i][i + n - 1]);
    }
    cout << minv << endl << maxv;
    return 0;
}

能量项链

题目要求

题目描述:

image.png

输入格式:

image.png

输出格式:

输出只有一行,是一个正整数E,为一个最优聚合顺序所释放的总能量。

数据范围:

image.png

输入样例:

4
2 3 5 10

输出样例:

710

思路分析

是 环形石子合并 的一个升级,思路还是一致的,对应到代码上有一些微处理,比如合并的长度最少是3,区间dp间断点的枚举必须从 l + 1  进行枚举

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 210;
int f[N][N];
int w[N];
int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> w[i], w[i + n] = w[i];
    for (int len = 3; len <= n + 1; len ++ )
        for (int l = 1; l + len - 1 <= 2 * n; l ++ )
        {
            int r = l + len - 1;
            for (int k = l + 1; k < r; k ++ )
                f[l][r] = max(f[l][r], f[l][k] + f[k][r] + w[l] * w[k] * w[r]);
        }
    int maxv = 0;
    for (int i = 1; i <= n; i ++ ) maxv = max(maxv, f[i][i + n]);
    cout << maxv << endl;
    return 0;
}




目录
相关文章
|
存储 资源调度 安全
H3C CAS系列 一、CAS初认识
对于虚拟化,可能第一时间大家想到的是虚拟机,而对于虚拟机大家可能第一时间想到的就是我们大多数人都可能比较熟悉的VMware系列产品,比如常用VMware Workstation Pro 、VMware esxi。 而今天我带大家一起认识一款我们国产的虚拟化软件 H3C CAS。
2918 0
|
关系型数据库 定位技术 数据库
空间数据中台是什么,怎么用?DataQ空间智能全面开放邀测
阿里云空间数据中台不等同于GIS,它是在DataQ数据资源平台中体系化的整合了空间数据的处理能力,用于空间数据治理和空间领域数字化转型需要。DataQ空间智能包括空间数据同步、空间数据查询和浏览、空间数据管理、空间数据服务和空间数据资产管理等能力。用户可以通过阿里云官网注册账号并开通DataQ的试用白名单来使用DataQ空间智能。在使用过程中,需要注意空间数据源的配置、zip压缩方式、计算集群的设置等问题。DataQ空间智能公共云的开通,将大幅度降低体验和试用的门槛和成本,为线下项目的选型做好准备;同时仍然需要一定的技术投入和耐心,但数字化转型是未来的大势所趋,空间数据中台是必然的选择。
空间数据中台是什么,怎么用?DataQ空间智能全面开放邀测
|
存储 运维 监控
当游戏爱上MongoDB!阿里云&MongoDB中国区域游戏行业私享会
始于2019年底的新冠疫情改变了我们的生活方式,游戏成为了很多人排遣寂寞的一种方式,由此带来了游戏市场的异常火爆。游戏市场比拼的是谁能更快速地开发迭代,让玩家体验更佳,因此能够敏捷开发、快速扩展、全球部署和轻运维的数据库产品无疑将为游戏的开发和后期运营奠定良好的基础。 诚邀您与Mongo DB、阿里云数据库专家团队, 以及游戏行业同行共同探讨如何使用Mongo DB帮您打造全球化高效、易用、稳定的数据库架构,并为您详细解读MongoDB5.0新特性在游戏行业的最佳实践。
4656 1
当游戏爱上MongoDB!阿里云&MongoDB中国区域游戏行业私享会
|
机器学习/深度学习 人工智能 自然语言处理
智能自动化全方位解读:定义、技术、市场、应用,一文解答所有
智能自动化融合AI与RPA技术,重塑企业效率。它可处理非结构化数据、跨系统协同、自主决策,广泛应用于财务、人力、制造等领域,助力降本增效、合规创新。2025年全球市场规模将达4200亿美元,中国超9500亿元,成为最大单一市场。实在Agent等标杆产品实现“一句话完成工作”,5000+企业已落地应用,部署快、回报高、无需改造系统,正推动人机协同的数字革命。
842 154
|
12月前
|
运维 安全 Linux
优雅告别系统(Linux用户退出脚本全解析)
本文教你如何编写Linux用户退出脚本,确保安全退出会话、清理资源并记录日志。涵盖基础命令(exit/logout)、脚本编写、自动触发与最佳实践,适合新手和运维人员提升系统安全性。
|
存储 SQL 人工智能
阿里云ODPS 使用实践的深度总结
本内容深入解析ODPS在大数据实践中的核心价值与挑战,涵盖分布式架构、流批一体、成本控制等关键技术,结合制造业、营销等场景案例,展示从数据治理到智能决策的跃迁路径,并展望未来边缘协同、AI平民化等前沿方向。
787 2
|
8月前
|
JSON 算法 API
通过京东开放平台API根据商品ID获取商品详情技术指南
本文详解京东开放平台商品详情API调用:从注册账号、获取App Key/Secret,到签名生成、Python代码实现及错误处理,涵盖准备工作、接口参数、完整示例与安全注意事项,助开发者快速可靠接入。(239字)
如何使用控制台群发短信 | 阿里云短信服务
操作指南|通过控制台群发短信
1747 14
|
移动开发 安全 Java
Android历史版本与APK文件结构
通过以上内容,您可以全面了解Android的历史版本及其主要特性,同时掌握APK文件的结构和各部分的作用。这些知识对于理解Android应用的开发和发布过程非常重要,也有助于在实际开发中进行高效的应用管理和优化。希望这些内容对您的学习和工作有所帮助。
2033 83
|
Java 应用服务中间件 Docker
java-web部署模式概述
本文总结了现代 Web 开发中 Spring Boot HTTP 接口服务的常见部署模式,包括 Servlet 与 Reactive 模型、内置与外置容器、物理机 / 容器 / 云环境部署及单体与微服务架构,帮助开发者根据实际场景选择合适的方案。
861 25