当前位置: 首页 > news >正文

DP(4)--区间DP

将n(1≤n≤200)堆石子绕圆形操场摆放,现要将石子有次序地合并成一堆。
规定每次只能选相邻的两堆石子合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分。 
(1)选择一种合并石子的方案,使得做n-1次合并,得分的总和最小。 
(2)选择一种合并石子的方案,使得做n-1次合并,得分的总和最大
输入
4
4 5 9 4
输出
43
54

线性结构是N个数据元素以有序的方式排列。访问线性结构一般采用由前至后的遍历方法。
线性动态规划就是在线性数据的基础上,通过某种递推方式(状态转移方程)得到最终结构的一种规划算法。
sum[i]: 从第1堆到第i堆石子数总和
fmax[i][j]: 从第i堆石子合并到第j堆石子的最大得分
fmin[i][j]: 从第i堆石子合并到第j堆石子的最小得分

初始化: fmax[i][i] = 0, fmin[i][i]= INF
状态方程:
fmax[i][j] = max{fmax[i][k]+fmax[k+1][j]+sum[j]-sum[i-1]} i <= k < j
fmin[i][j] = min{fmin[i][k]+fmin[k+1][j]+sum[j]-sum[i-1]} i <= k < j

由于题中围成一个环,我们将这条链再延长一倍,变成2*n堆,地中第i堆与第n+i堆相同,
动态规划求解后,答案为f(1,n), f(2,n+1), ... , f(n-1,2*n-2)中的最优解

状态转移
要计算f(i,j)的值时需知道所有f(i,k)和f(k+1,j)的值,
以len=j-i+1作为DP 的区间长度,从小到大枚举len,
然后枚举i的值,根据len和i用公式计算出j的值,然后枚举k,时间复杂度为O(n^3)

/*  https://loj.ac/problem/10147  */
#include <iostream>
using namespace std;

const int MAXN = 201;
const int INF = 0x3f3f3f3f;
int arr[2*MAXN];
int sum[2*MAXN];
int fmax[2*MAXN][2*MAXN];
int fmin[2*MAXN][2*MAXN];

int main()
{
    int i, j, k, n, len;
    cin >> n;
    for (i = 1; i <= n; ++i)
    {
        cin >> arr[i];
        arr[n+i] = arr[i]; 
    }
    for (i = 1; i <=(n<<1); ++i)
        sum[i] = sum[i-1] + arr[i];

    for (len = 2; len <= n; ++len)
        for (i = 1; i <= (n<<1)-len+1; ++i)
        {
            j = i + len - 1;
            // 初始化
            fmax[i][j] = 0;
            fmin[i][j] = INF;
            for (k = i; k < j; ++k)
            {
                fmax[i][j] = max(fmax[i][j], fmax[i][k] + fmax[k+1][j] + sum[j] - sum[i-1]);
                fmin[i][j] = min(fmin[i][j], fmin[i][k] + fmin[k+1][j] + sum[j] - sum[i-1]);
            }
        }

    int ansmax = 0, ansmin = INF;
    for (i = 1; i < n; ++i)
    {
        ansmax = max(ansmax, fmax[i][i+n-1]);
        ansmin = min(ansmin, fmin[i][i+n-1]);
    }

    cout << ansmin << endl << ansmax << endl;


    return 0;
}


四边形不等式优化请参考

https://oi-wiki.org/dp/opt/quadrangle/

https://www.cnblogs.com/a1b3c7d9/p/10984353.html

dp[i][j]=min{dp[i][k]+dp[k+1][j]+w[i][j]} (i≤k<j)
把dp[i][k]+dp[k+1][j]取得最值的那个k, 称为dp[i][j]的最优决策点。

 

 

#include <iostream>
using namespace std;
const int MAXN = 201;
const int INF = 0x3f3f3f3f;
int arr[2*MAXN];
int sum[2*MAXN];
int fmax[2*MAXN][2*MAXN];
int fmin[2*MAXN][2*MAXN];
int ma[2*MAXN][2*MAXN]; //ma[i][j]: 从第i堆石子合并到第j堆石子的最大得分时的最优决策点
int mi[2*MAXN][2*MAXN]; //mi[i][j]: 从第i堆石子合并到第j堆石子的最小得分时的最优决策点

int main()
{
    int i, j, k, n, len, t;
    cin >> n;
    for (i = 1; i <= n; ++i)
    {
        cin >> arr[i];
        arr[n+i] = arr[i];
    }
    for (i = 1; i <=(n<<1); ++i)
    {
        sum[i] = sum[i-1] + arr[i];
        ma[i][i] = i;
        mi[i][i] = i;
    }

    for (len = 2; len <= n; ++len)
        for (i = 1; i <= (n<<1)-len+1; ++i)
        {
            j = i + len - 1;
            // 初始化
            fmax[i][j] = 0;
            fmin[i][j] = INF;
            // 四边形不等式优化
            for (k = ma[i][j-1]; k <= ma[i+1][j] && k < j; ++k)
            {
                t = fmax[i][k] + fmax[k+1][j] + sum[j] - sum[i-1];
                if (fmax[i][j] < t)
                {
                    fmax[i][j] = t;
                    ma[i][j] = k;
                }
            }

            for (k = mi[i][j-1]; k <= mi[i+1][j] && k < j; ++k)
            {
                t = fmin[i][k] + fmin[k+1][j] + sum[j] - sum[i-1];
                if (fmin[i][j] > t)
                {
                    fmin[i][j] = t;
                    mi[i][j] = k;
                }
            }
        }

    int ansmax = 0, ansmin = INF;
    for (i = 1; i < n; ++i)
    {
        ansmax = max(ansmax, fmax[i][i+n-1]);
        ansmin = min(ansmin, fmin[i][i+n-1]);
    }

    cout << ansmin << endl << ansmax << endl;


    return 0;
}
 

相关文章:

DP(4)--区间DP

将n(1≤n≤200)堆石子绕圆形操场摆放&#xff0c;现要将石子有次序地合并成一堆。 规定每次只能选相邻的两堆石子合并成新的一堆&#xff0c;并将新的一堆的石子数&#xff0c;记为该次合并的得分。 (1)选择一种合并石子的方案&#xff0c;使得做n-1次合并&#xff0c;得分的总…...

【C语言】“qsort函数详解”与“使用冒泡思想模拟使用qsort”

✨✨✨✨如果文章对你有帮助记得点赞收藏关注哦&#xff01;&#xff01;✨✨✨✨ 文章目录✨✨✨✨如果文章对你有帮助记得点赞收藏关注哦&#xff01;&#xff01;✨✨✨✨qsort的介绍&#xff1a;一、qsort函数的使用✨比较int类型数据比较字符型数据比较结构体数据冒泡思想…...

接口自动化框架---升级版(Pytest+request+Allure)

目录&#xff1a;导读 一、简单介绍 二、目录介绍 三、代码分析 写在最后 接口自动化是指模拟程序接口层面的自动化&#xff0c;由于接口不易变更&#xff0c;维护成本更小&#xff0c;所以深受各大公司的喜爱。 第一版入口&#xff1a;接口自动化框架(PytestrequestAllure…...

C语言循环语句简述

C 循环 有的时候&#xff0c;我们可能需要多次执行同一块代码。一般情况下&#xff0c;语句是按顺序执行的&#xff1a;函数中的第一个语句先执行&#xff0c;接着是第二个语句&#xff0c;依此类推。 编程语言提供了更为复杂执行路径的多种控制结构。 循环语句允许我们多次…...

STM32开发(16)----CubeMX配置DMA

CubeMX配置DMA前言一、什么是DMA&#xff1f;二、实验过程1.CubeMX配置2.代码实现3.实验结果总结前言 本章介绍使用STM32CubeMX对DMA进行配置的方法&#xff0c;DMA的原理、概念和特点&#xff0c;配置各个步骤的功能&#xff0c;并通过串口DMA传输实验方式验证。 一、什么是…...

让物流园区可视可控,顺丰供应链与亚马逊云科技的供应链新解法

导读&#xff1a;物流园区如何破解供应链断点&#xff1f;在物流园区附近&#xff0c;我们经常看到周边道路停满了集装箱卡车。这是物流园区的一个典型痛点&#xff0c;由于园区内部业务情况的不可见性&#xff0c;司机们往往到了园区才被告知业务繁忙&#xff0c;需要长时间排…...

2023年3月北京/西安/广州/深圳DAMA-CDGA/CDGP数据治理认证报名

DAMA认证为数据管理专业人士提供职业目标晋升规划&#xff0c;彰显了职业发展里程碑及发展阶梯定义&#xff0c;帮助数据管理从业人士获得企业数字化转型战略下的必备职业能力&#xff0c;促进开展工作实践应用及实际问题解决&#xff0c;形成企业所需的新数字经济下的核心职业…...

「TCG 规范解读」TCG 主规范-设计原则

可信计算组织(Ttrusted Computing Group,TCG)是一个非盈利的工业标准组织,它的宗旨是加强在相异计算机平台上的计算环境的安全性。TCG于2003年春成立,并采纳了由可信计算平台联盟(the Trusted Computing Platform Alliance,TCPA)所开发的规范。现在的规范都不是最终稿,都…...

【Spring源码】Spring AOP的核心概念

废话版什么是AOP关于什么是AOP&#xff0c;这里还是要简单介绍下AOP&#xff0c;Aspect Oriented Programming&#xff0c;面向切面编程&#xff0c;通过预编译和运行期间提供动态代理的方式实现程序功能的统一维护&#xff0c;使用AOP可以降低各个部分的耦合度&#xff0c;提高…...

华为OD机试用Python实现 -【任务混部】(2023-Q1 新题)

华为OD机试题 华为OD机试300题大纲任务混部题目输入输出示例一输入输出说明示例二输入输出说明备注Code代码编写思路华为OD机试300题大纲 参加华为od机试,一定要注意不要完全背诵代码,需要理解之后模仿写出,通过率才会高。 华为 OD 清单查看地址:blog.csdn.net/hihell/ca…...

Linux yum 命令

yum&#xff08; Yellow dog Updater, Modified&#xff09;是一个在 Fedora 和 RedHat 以及 SUSE 中的 Shell 前端软件包管理器。 基于 RPM 包管理&#xff0c;能够从指定的服务器自动下载 RPM 包并且安装&#xff0c;可以自动处理依赖性关系&#xff0c;并且一次安装所有依赖…...

package.json 字段配置

文章目录环境导入相关main 和 modulewebpack resolve.mainFieldsbrowserexports定义其他模块根据导入语句导出嵌套环境导出vue中 exports 用法自定义运行环境环境导入相关 main 和 module 根据导入模块时不同的模块规范语句查找不同的入口文件 "main": "dist…...

springboot中集成redis,二次封装成工具类

大家好&#xff0c;我是雄雄&#xff0c;欢迎关注微信公众号&#xff1a;** 雄雄的小课堂 ** 现在是&#xff1a;2023年2月28日11:01:56 前言 redis大家应该都不陌生&#xff0c;我们在好多场景下都会使用&#xff0c;最近在面试别人的时候&#xff0c;也会问一些关于redis的…...

Linux Vim 简介

文章目录01. 编辑器 Gedit 介绍02. 什么是 Vi(Vim)03. vim工作模式4.1 命令模式4.2 编辑模式4.3 末行模式04. vim教程05. vim基本操作06. vim实用操作7.1 命令模式下的操作7.2 末行模式下的操作01. 编辑器 Gedit 介绍 gedit 是一个 GNOME 桌面环境下兼容 UTF-8 的 文本编辑器。…...

软件测试面试题 —— 整理与解析(2)

&#x1f60f;作者简介&#xff1a;博主是一位测试管理者&#xff0c;同时也是一名对外企业兼职讲师。 &#x1f4e1;主页地址&#xff1a;&#x1f30e;【Austin_zhai】&#x1f30f; &#x1f646;目的与景愿&#xff1a;旨在于能帮助更多的测试行业人员提升软硬技能&#xf…...

HashMap与Hashtable的这九个区别,你知道吗

Hashtable Hashtable是原始的java.util的一部分&#xff0c;属于一代集合类&#xff0c;是一个Dictionary具体的实现 。Java1.2重构的Hashtable实现了Map接口&#xff0c;因此&#xff0c;Hashtable现在集成到了集合框架中。它和HashMap类很相似。 Hashtable与HashMap的区别 …...

Java奠基】掌握Java基础知识

目录 常见字面量 特殊字面量 数据类型 标识符 键盘录入 常见字面量 字面量就是数据在程序中的书写格式&#xff0c;字面量的分类如下&#xff1a; 字面量类型说明举例整数类型不带小数点的数字12&#xff0c;25小数类型带小数点的数字3.14&#xff0c;-5&#xff0c;20…...

Hive窗口函数-lead/lag函数

前面我们学习的first_value和last_value 取的是排序后的数据截止当前行的第一行数据和最后一行数据 Lag和Lead分析函数可以在一次查询中取出当前行后N行和前N行的数据&#xff0c;虽然可以不用排序&#xff0c;但是往往只有在排序的场景下取前面或者后面N 行数据才有意义 这种…...

2023JAVA面试题全集超全面超系统超实用!早做准备早上岸

2022年我凭借一份《Java面试核心知识点》成功拿下了阿里、字节、小米等大厂的offer&#xff0c;两年的时间&#xff0c;为了完成我给自己立的flag&#xff08;拿下一线互联网企业offer大满贯&#xff09;&#xff0c;即使在职也一直在不断的学习与备战面试中&#xff01;——或…...

FreeRTOS入门(05):事件组

文章目录目的基础说明相关函数使用演示总结目的 事件组是RTOS中相对常用的用于任务间交互的功能&#xff0c;这篇文章将对相关内容做个介绍。 本文代码测试环境见前面的文章&#xff1a;《FreeRTOS入门&#xff08;01&#xff09;&#xff1a;基础说明与使用演示》 基础说明…...

3.3.1_1 检错编码(奇偶校验码)

从这节课开始&#xff0c;我们会探讨数据链路层的差错控制功能&#xff0c;差错控制功能的主要目标是要发现并且解决一个帧内部的位错误&#xff0c;我们需要使用特殊的编码技术去发现帧内部的位错误&#xff0c;当我们发现位错误之后&#xff0c;通常来说有两种解决方案。第一…...

k8s业务程序联调工具-KtConnect

概述 原理 工具作用是建立了一个从本地到集群的单向VPN&#xff0c;根据VPN原理&#xff0c;打通两个内网必然需要借助一个公共中继节点&#xff0c;ktconnect工具巧妙的利用k8s原生的portforward能力&#xff0c;简化了建立连接的过程&#xff0c;apiserver间接起到了中继节…...

[Java恶补day16] 238.除自身以外数组的乘积

给你一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O(n) 时间复杂度…...

【HarmonyOS 5 开发速记】如何获取用户信息(头像/昵称/手机号)

1.获取 authorizationCode&#xff1a; 2.利用 authorizationCode 获取 accessToken&#xff1a;文档中心 3.获取手机&#xff1a;文档中心 4.获取昵称头像&#xff1a;文档中心 首先创建 request 若要获取手机号&#xff0c;scope必填 phone&#xff0c;permissions 必填 …...

【7色560页】职场可视化逻辑图高级数据分析PPT模版

7种色调职场工作汇报PPT&#xff0c;橙蓝、黑红、红蓝、蓝橙灰、浅蓝、浅绿、深蓝七种色调模版 【7色560页】职场可视化逻辑图高级数据分析PPT模版&#xff1a;职场可视化逻辑图分析PPT模版https://pan.quark.cn/s/78aeabbd92d1...

NXP S32K146 T-Box 携手 SD NAND(贴片式TF卡):驱动汽车智能革新的黄金组合

在汽车智能化的汹涌浪潮中&#xff0c;车辆不再仅仅是传统的交通工具&#xff0c;而是逐步演变为高度智能的移动终端。这一转变的核心支撑&#xff0c;来自于车内关键技术的深度融合与协同创新。车载远程信息处理盒&#xff08;T-Box&#xff09;方案&#xff1a;NXP S32K146 与…...

Redis:现代应用开发的高效内存数据存储利器

一、Redis的起源与发展 Redis最初由意大利程序员Salvatore Sanfilippo在2009年开发&#xff0c;其初衷是为了满足他自己的一个项目需求&#xff0c;即需要一个高性能的键值存储系统来解决传统数据库在高并发场景下的性能瓶颈。随着项目的开源&#xff0c;Redis凭借其简单易用、…...

STM32---外部32.768K晶振(LSE)无法起振问题

晶振是否起振主要就检查两个1、晶振与MCU是否兼容&#xff1b;2、晶振的负载电容是否匹配 目录 一、判断晶振与MCU是否兼容 二、判断负载电容是否匹配 1. 晶振负载电容&#xff08;CL&#xff09;与匹配电容&#xff08;CL1、CL2&#xff09;的关系 2. 如何选择 CL1 和 CL…...

Golang——7、包与接口详解

包与接口详解 1、Golang包详解1.1、Golang中包的定义和介绍1.2、Golang包管理工具go mod1.3、Golang中自定义包1.4、Golang中使用第三包1.5、init函数 2、接口详解2.1、接口的定义2.2、空接口2.3、类型断言2.4、结构体值接收者和指针接收者实现接口的区别2.5、一个结构体实现多…...

抽象类和接口(全)

一、抽象类 1.概念&#xff1a;如果⼀个类中没有包含⾜够的信息来描绘⼀个具体的对象&#xff0c;这样的类就是抽象类。 像是没有实际⼯作的⽅法,我们可以把它设计成⼀个抽象⽅法&#xff0c;包含抽象⽅法的类我们称为抽象类。 2.语法 在Java中&#xff0c;⼀个类如果被 abs…...