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

AT_abc201_f [ABC201F] Insertion Sort 题解

link

题目给出了 \(1\)\(n\) 的一组排列 \(x_1,x_2...x_n\),并对于第 \(i\) 个数 \(1\le i \le n\) 给出三个操作:

  1. 花费 \(A_i\) 的代价,把第 \(i\) 个数移动到任意位置。
  2. 花费 \(B_i\) 的代价,把第 \(i\) 个数移动到最左边。
  3. 花费 \(C_i\) 的代价,把第 \(i\) 个数移动到最右边。

可以进行无数次操作,求经过若干次操作后把该排列按从小到大排序需要到最小代价是多少?

对于这种给出不同操作不同代价,并最终要求达成某种目的题目,比较容易想到可能需要通过 \(dp\) 来寻找最优解,我们先尝试能否设计出正确的 \(dp\) 状态和复杂度能够接受的状态转移。

开始思考之前,我们发现题目中给出的“向左移”和“向右移”操作是一种比较受限制的操作,而“任意移动”相对自由,我们尽可能地希望使用受限制的操作时的代价比自由的操作更小,因此可以考虑将每个 \(B_i\)\(C_i\)\(A_i\)\(\min\),这样至少保证受限制的操作的代价不劣。否则太亏(

现在考虑 \(dp\) 的阶段可以用什么来划分,但好像直接去简单地划分并不好做,如第 \(i\) 个位置前排好序的最小代价,我们不好得知在局部排好序后的具体形态,也不能从这样的子问题转移到更大的问题,我们还是先来发掘一些性质。

有一个不难理解的结论:在最优的操作方案中必然会有一个数字是没有移动的,否则可以通过固定一个“向左移动的最大数”或者”向右移动的最小数”来减少一个人的消耗,在排好序后,这些人不用动也会处于一个正确的相对位置。

这一结论是基于值域的,我们可以尝试把 \(dp\) 阶段设为规定值为 \(x\) 的数字不动,再把整个序列排好序最小代价,显然存在一种方案,可以将小于 \(x\) 的数按从大到小的顺序放到最左边,把大于 \(x\) 的数字按从小到大的顺序放到最右边,这样的操作方案肯定是合法的,但这样就没有用到“任意移动”的操作,也好像没什么办法去转移。

我们尝试结论加强:最优方案中不止是一个数没有移动,可能是所给排列中的一个上升子序列没有被移动,显然这样的上升子序列的相对位置是正确的,可以将值小于上升子序列中第一个数的都按顺序放最左边,值大于上升子序列中最后一个数的都按顺序放最右边,值出于上升子序列中间的使用“任意移动”的操作排序。

这一结论直接启发我们的状态设计和转移,我们可以与刚才一样以值域作为 \(dp\) 的阶段,为了方便转移,状态重新表述为:\(dp_x\) 表示把值域在 \([1,x]\) 区间内的数字排好序所需要的最小代价。

状态转移方程为(以下的 \(p_x\) 表述为数字 \(x\) 在排序前所处的位置):

\[dp_x= \min \{\sum_{i=1}^{x-1}b_i,\min_{\large y < x,p_y<p_x} (dp_y+\sum_{k=y+1}^{x-1}A_k) \} \]

可以形象化地理解一下这一转移:相当于我们在排序前的数列选择了两个数作为不进行移动的上升子序列的头与尾(要满足上升子序列的条件,故 \(y < x,p_y<p_x\)),\(dp_y\) 中已经把 \([1,y]\) 中的数排好序,再按照原来的方案进行操作就需要将值在 \([y+1,x-1]\) 区间内的数字“任意移动”,同时最优方案也可能只有 \(x\) 一个数没有移动,所以也要和最初的移动方案(小于 \(x\) 的全“向左移”)取最小值。

转移的后半部分是二维偏序,用线段树可以优化,具体来说就是因为 \(y\) 是定值,把 \(dp_y-\sum_{i=1}^{y}\) 存入数据结构中即可,前缀和优化应该是大家的被动技能,就不说了

\(dp\) 初值全为正无穷,答案为 \(\min (dp_x+\sum_{i=x+1}^{n} C_i)\)。(因为 \(dp\) 状态中没有将后半部分排序)

时间复杂度 \(O(n \log n)\)

using namespace std;
const int N=2e5+5;
const int inf=0x3f3f3f3f3f3f3f3f;
int n,p[N],suma[N],sumb[N],sumc[N],dp[N],ans=inf;
int t[N*3],P=1;
void update(int pos,int v){int x=pos+P;t[x]=v;for(x>>=1;x;x>>=1) t[x]=min(t[ls(x)],t[rs(x)]);
}
int query(int l,int r){int res=inf;l+=P-1,r+=P+1;while(l^1^r){if(~l&1) res=min(res,t[l^1]);if(r&1) res=min(res,t[r^1]);l>>=1,r>>=1;}return res;
}
void xpigeon(){rd(n);memset(t,0x3f,sizeof(t));while(P<=n+1) P<<=1;for(int i=1,x;i<=n;i++){rd(x);p[x]=i;}for(int i=1,a,b,c;i<=n;i++){rd(a,b,c);suma[i]=suma[i-1]+a;sumb[i]=sumb[i-1]+min(a,b);sumc[i]=sumc[i-1]+min(a,c);}for(int i=1;i<=n;i++){dp[i]=min(sumb[i-1],query(1,p[i])+suma[i-1]);ans=min(ans,dp[i]+sumc[n]-sumc[i]);update(p[i],dp[i]-suma[i]);}cout<<ans<<'\n';
}
signed main() {ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);xpigeon();return 0;
}
http://www.hskmm.com/?act=detail&tid=15453

相关文章:

  • .NET国产化改造探索(三)、银河麒麟安装.NET 8环境
  • c语言动态内存分配
  • 2025.9.24——1橙
  • AT_arc172_d [ARC172D] Distance Ranking
  • Python爬虫实现大乐透历史数据抓取
  • 【读书笔记】《深入理解计算机系统(原书第三版)》第一章 计算机系统漫游
  • 如何将PPT每一页批量导出为高清JPG图片?一文讲清处理流程
  • 实用指南:计算机视觉:基于YOLOv11 实例分割与OpenCV 在 Java 中的实现图像实例分割
  • Java实现双色球历史是否中奖查询
  • ABC424 游记(VP)
  • Java实现大乐透历史是否中奖查询
  • 阿德勒的课题分离是很好用的东西
  • 别再混淆 PHP8.1 中纤程 Fibers 和协程 Coroutines 了 一文搞懂它们的区别
  • 主要测试的测试用例
  • 详细介绍Seata的AT模式分布式事务
  • VMware VeloCloud 漏洞分析:未授权远程代码执行全链条攻破
  • 【GitHub每日速递 250924】18 个 AI 投资大师齐上阵!这个开源对冲基金让你看透市场底牌
  • HJ9 提取不重复的整数
  • 2025年国家科技奖初评公布(科技进步奖)
  • 2025年国家科技奖初评公布(科技发明奖)
  • 12
  • 2025年国家科技奖初评公布(自然科学奖)
  • 近端策略优化算法PPO的核心概念和PyTorch实现详解
  • JAX快速上手:从NumPy到GPU加速的Python高性能计算库入门教程
  • Memento:基于记忆无需微调即可让大语言模型智能体持续学习的框架
  • 记录一次附加属性失效全过程
  • Java 与物联网(IoT):边缘计算与智能终端应用
  • 为你的数据选择合适的分布:8个实用的概率分布应用场景和选择指南
  • AI 落地应用最新工具集
  • 台风呢