一直搞不明白这东西自身的正确性。我更愿意将其理解为模拟费用流或者某种dp优化，事实上证明正确性的时候往往也是这么证的。
基于dp优化的理解
AT_dwango2016qual_e
令 \(dp_{i,j}\) 表示 i 时刻在位置 j 的最小代价。
转移：
\[dp_{i,j}=min_{k<=j}(dp_{i-1,k})+ ( i 时间内在位置 j 所有烟花的不满值之和) \]令 \(dp'_{i,j}=min_{k<=j}(dp_{i,k})\) (就是做了一个前缀min)
\(dp_{i,j}=dp'_{i-1,j}+\) ( \(i\) 时间内在位置 \(j\) 所有烟花的不满值之和)
\(dp'_{i,j}=min(dp'_{i,j-1},dp_{i,j})\)
从“ \(i\) 时间内在位置 \(j\) 所有烟花的不满值之和”入手，令\(f(i)\)表示在 \(i\) 位置，某一烟花造成的不满值。我们可以发现， $f(i)=|x_i-i| $( \(x_i\) 表示烟花绽放的位置) 。
显然，\(f(i)\)是一个下凸函数,那么对于在同一时刻绽放的所有烟花，\(f(i)\)的和也为下凸函数。(若干个下凸函数的和仍然是下凸函数)
考虑我们的 \(dp\) 过程，是先加了同一时刻绽放的所有烟花的不满值的和，然后做了一遍前缀min，然后重复。
最开始 dp 函数是一条 \(y=0\) 的直线，加上 同一时刻绽放的所有烟花的不满值的和(一个下凸函数)之后仍是一个下凸函数，然后做一遍前缀min，仍然是一个下凸函数，而且对于下凸函数取min就是把后面一段导数大于0的一段的导数改为0。
这就是经典的slope trick。归纳证明dp函数是一个凸函数，进而维护差分数组。
为什么要把这个题放在反悔贪心里？看看这个。还没看懂，懂的佬拜托教教我qaq。
2024年华为杯广东工业大学程序设计竞赛（同步赛）B
跟上一题类似，设到第i个元素为止，通过j关的最小总损耗生命值。归纳证明其凸性。拿一个堆维护差分数组。
反悔贪心的理解（搬运官方题解）：
作者：\(o\)
链接：https://ac.nowcoder.com/discuss/1282761?type=101&order=0&pos=4&page=0&channel=-1&source_id=1
来源：牛客网
考虑反悔贪心，用一个大顶堆存挑战过的挑战房间所消耗的生存值。
一、首先奖励房间是一定会拿的。
二、假如到一个挑战房间：
1.可以挑战，那么就贪心的通关房间i，然后将其放入大顶堆中。
2.无法挑战，如果之前通关过挑战房间，就比较堆顶和房间的消耗的生存值，假如撤销后可以挑战当前房间，那么就挑战，将之前挑战的某个房间撤销；否则放弃挑战这个房间。在之前没有通关过挑战房间则只能放弃。
三、如果到了一个事件房间：
1.可以挑战，但是不放入大顶堆。
2.不可挑战，和前面类似，比较堆顶和房间消耗的生存值，不过由于不能放弃，就要一直放弃之前通关的挑战房间，直到这个房间可以通关。如果堆空了也无法通关，就直接退出。
尽管事件房间可能会导致之前挑战的所有房间都被撤销，但是只要能通关这个事件房间，都有可能有更大的答案，所以每一步都要取max，最后答案就是全局最大值。
基于模拟费用流的理解
ccpcf2024 G
场上被这个题创似了。
标签：min,挑战,房间,凸函数,反悔,通关,dp,贪心 From： https://www.cnblogs.com/thedreammaker/p/18124192