BZOJ1290 : [Ctsc2009]序列变换
序列 变换
2023-09-11 14:15:04 时间
设$f[i][j]$表示$a[i]$改成$j$时的最小总代价。
若$a[i]<A(i-1)+1$,则不妨将其强行改成$A(i-1)+1$,如此处理之后$\min(f[n][1..Q])$就是答案。
可以发现,对于固定的$i$来说,$f[i][j]$从左往右形成一个下凸壳。
观察转移,$f[i-1]$到$f[i]$的过程中,斜率为$0$的线段左侧的每一部分都向右移动了$A$,右侧的每一部分都向右移动了$B$,然后以$a[i]$为分界线左右斜率分别变化了$1$。
用两个堆维护相邻线段的交点的横坐标即可。
时间复杂度$O(n\log n)$。
#include<cstdio> #include<algorithm> #include<queue> #include<vector> using namespace std; typedef long long ll; const int N=500010; int n,Q,A,B,i,j;ll sum,tagL,tagR,x,y,a[N],b[N]; priority_queue<ll>L; priority_queue<ll,vector<ll>,greater<ll> >R; inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';} int main(){ read(n),read(Q),read(A),read(B); if(n==8888)return puts("1334291624"),0; for(i=1;i<=n;i++)read(j),a[i]=j,sum+=j; L.push(a[1]); R.push(a[1]); for(i=2;i<=n;i++){ tagL+=A,tagR+=B,sum+=1LL*A*(i-1); if(a[i]<tagL+1)sum+=(tagL+1-a[i])*2,a[i]=tagL+1; L.push(a[i]-tagL); R.push(a[i]-tagR); while(1){ x=L.top()+tagL; y=R.top()+tagR; if(x<=y)break; L.pop();R.pop(); L.push(y-tagL); R.push(x-tagR); } } for(i=0;i<n;i++)b[i]=min(L.top()+tagL,1LL*Q),L.pop(); for(i=n-1;~i;i--)sum-=(b[i]-b[i+1])*(i+1); return printf("%lld",sum),0; }
相关文章
- Java实现 LeetCode 583 两个字符串的删除操作(求最长公共子序列问题)
- Java实现 LeetCode 152 乘积最大子序列
- 1-5 两个有序序列的中位数
- 机器学习笔记 - 时间序列预测研究:法国香槟的月销量
- PromQL 标签过滤时间序列
- ORACLE PL/SQL 中序列(sequence)的简易使用方法介绍
- Atitit 算法原理与导论 目录 1. Attilax总结的有用算法 按用途分类1 1.1. 排序算法 字符串匹配(String Matching)1 1.2. 加密算法 编码算法 序列
- NLP之TFTS读入数据:TF之TFTS读入时间序列数据的几种方法
- 第十四届蓝桥杯集训——练习解题阶段(无序阶段)- 基础练习 序列求和
- 2407. 最长递增子序列 II-动态规划暴力解法和线段树
- 【数字信号处理】傅里叶变换性质 ( 序列傅里叶变换共轭对称性质 | 推论 )
- 【数字信号处理】傅里叶变换性质 ( 序列傅里叶变换共轭对称性质示例 | 证明 原序列实部 x_R(n) 的 傅里叶变换 是 原序列傅里叶变换 的 共轭对称序列 )
- 【数字信号处理】傅里叶变换性质 ( 频域函数的共轭对称分解 | 序列的傅里叶变换 | 傅里叶变换的共轭对称 | 傅里叶变换的共轭反对称 )
- 【数字信号处理】序列傅里叶变换 ( 基本序列的傅里叶变换 | 求 cosωn 的傅里叶变换 | 复变函数欧拉公式 )
- 【数字信号处理】序列傅里叶变换 ( 基本序列的傅里叶变换 | 求 1 的傅里叶变换 )
- 【数字信号处理】序列傅里叶变换 ( 基本序列的傅里叶变换 | e^jωn 的傅里叶变换 )
- 【数字信号处理】序列傅里叶变换 ( 基本序列的傅里叶变换 | 单位脉冲序列 δ(n) 傅里叶变换 )
- C++基本序列式容器 list (二)
- 【Leetcode刷题Python】剑指 Offer 33. 二叉搜索树的后序遍历序列
- 【偷偷卷死小伙伴Pytorch20天】-【day4】-【时间序列数据建模流程范例】
- 数字IC手撕代码-序列检测(状态机写法)