首页 > 其他分享 >单调栈优化DP

单调栈优化DP

时间:2024-02-22 21:02:34浏览次数:23  
标签:min top xx DP 优化 单调

当有形如\(f_i=min_{j=0}^{l(i)}f_j+w转移代价\)

我们就可以使用单调栈优化DP

为什么不用单调队列???

当有形如\(f_i=min_{j=l(i)}^{i-1}f_j+w转移代价\)

我们就可以使用单调队列优化DP

至于为毛,就可以从它的工作原理上去分析

6305. 最小值

\(dp_i=min_{j=0}^{i-1}g_j+f(min_{x=j+1}^{i}a_x)\)

然后用单调栈转移

#include<bits/stdc++.h>
#define Fu(i,a,b) for(int i=(a);i<=(b);i++)
#define fre(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
using namespace std;
int n,x[200005],ls[200005],top;
long long f[200005],g[200005],mx[200005],a,b,c,d;
struct node{
	long long t;
	int xx;
}q[200005];
int main(){ 
	fre(min);
	scanf("%d%lld%lld%lld%lld",&n,&a,&b,&c,&d);
	Fu(i,1,n) scanf("%d",&x[i]),f[i]=a*x[i]*x[i]*x[i]+b*x[i]*x[i]+c*x[i]+d;;
	Fu(i,1,n){
		long long o=g[i-1]; 
		while(top&&x[q[top].xx]>=x[i]) o=max(o,q[top].t),top--;
		g[i]=o+f[i];
		if(top) g[i]=max(g[i],g[q[top].xx]);
		q[++top].t=o,q[top].xx=i;
	}
	printf("%lld",g[n]);
	return 0;
}

标签:min,top,xx,DP,优化,单调
From: https://www.cnblogs.com/zhy114514/p/18028150

相关文章

  • 动态DP
    动态DP最大子段和考虑设\(f_i\)表示以i为结尾的最大子段和,\(g_i\)表示i以内的最大子段和\[f_i=\max(f_{i-1}+a_i,a_i)\]\[g_i=\max(g_{i-1},f_i)\]然后非常容易将每个权值变成一个矩阵,然后每次修改就变成修改一个矩阵用线段树维护即可树上最大独立集(没有上司的舞会带修)考......
  • 《优化接口设计的思路》系列:第八篇—分页接口的设计和优化
    一、前言大家好!我是sum墨,一个一线的底层码农,平时喜欢研究和思考一些技术相关的问题并整理成文,限于本人水平,如果文章和代码有表述不当之处,还请不吝赐教。作为一名从业已达六年的老码农,我的工作主要是开发后端Java业务系统,包括各种管理后台和小程序等。在这些项目中,我设计过单/多......
  • CDN优化
    1.传统上传到应用2.通过应用下载,并发大所有流量都打到引用和出口带宽限制 采用cdn,大概是下面这个图这个流程,我们只需要配置cdn域名指向我们应用地址下载针对防止恶意下载可以使用cdn鉴权大概流程是这样鉴权逻辑说明CDN服务器接到资源访问请求后,判断最终生成鉴权URL请求......
  • 玉蟾宫(单调栈)
    玉蟾宫(单调栈)题目描述有一天,小猫rainbow和freda来到了湘西张家界的天门山玉蟾宫,玉蟾宫宫主蓝兔盛情地款待了它们,并赐予它们一片土地。这片土地被分成N*M个格子,每个格子里写着’R’或者’F’,R代表这块土地被赐予了rainbow,F代表这块土地被赐予了freda。现在freda要在这里......
  • 基于STM32F407MAC与DP83848实现以太网通讯二(DP83848硬件配置以及寄存器)
    参考内容:DP83848数据表一、PHYDP83848功能模块图                     DP83848的硬件模块主要为:MII/RMII/SNI INTERFACES:用于与MAC数据传输的MII/RMII/SNI接口Transmit BLOCK:数据发送模块,将从外部MAC(例如STM32ETH外设的MAC)接收......
  • 基于STM32F407MAC与DP83848实现以太网通讯一(STM32以太网(ETH)外设)
    STM32F4xx可以通过以太网按照IEEE802.3-2002标准发送和接收数据。支持与外部物理层(PHY)相连的两个工业标准接口:默认情况下使用的介质独立接口(MII)(在IEEE802.3规范中定义)和简化介质独立接口(RMII)。具体的以太网(ETM)特性参考:STM32F4xx中文参考手册这里将重要的地方进......
  • 玉蟾宫(悬线dp)
    求最大子矩阵一般用采用悬线法(包好用的牢底)悬线法:[以这道题为例,我们将R称为障碍格子,将F称为非障碍格子]我们选择任意一个非障碍格子,引出三条直线:左直右直上直随后从这个点出发,分别向上左右延申直到遇到障碍格我们要求上悬线尽可能高的面积,但有可能上一......
  • mysql面试高频问题---慢查询如何定位和优化⬆️
    优化-sql执行很慢,如何解决聚合查询:新增临时表多表查询:优化sql语句结构表数据量过大查询:添加索引深度分页查询解决方案一个SQL语句执行很慢,如何分析?可以采用EXPLAIN或者DESC命令获取MySQL如何执行SELECT语句的信息展示SQL执行的情况,部分字段说明如下:个人测试总结......
  • linux常用命令--dpkg
    dpkg是Debain系列linux发行版本中的重要命令,用于管理软件包,安装、配置、卸载等等。更多介绍请参考官方文档:www.dpkg.orgdpkg常用参数:dpkg-ipackage_file.deb安装指定软件包 dpkg-igvim.debdpkg-rpackage_file.deb删除以安装的软件包,但保留配置文件 dpkg-rgv......
  • dp 学习笔记 (2024/2/22 - )
    计数[ARC107D]NumberofMultisets[ARC104D]MultisetMean大值域限制偏序计数[CF1295F]GoodContest[ARC104E]RandomLIS......