题解：P10478 生日礼物

bianshiyang · 2025-04-11 19:22:49 · 题解

题目传送门

本篇篇幅较长，细节处证明居多，是本蒟蒻刚开始学习反悔贪心的笔记，希望能让很多初学者更好理解一点，也希望各位大佬可以耐心看完。

分析

感觉有点贪心的味道，但是没啥办法可以一直贪下去，于是考虑 DP，结果发现由于取的块数的限制，使得设出来的状态是二维的，即 f_{i,j} 表示前 i 个数划分成 j 个段所得到的最大代价，转移很好写，但状态数已经是 O(n^2) 的了，所以 DP 做不了，然后就猜到了反悔贪心，可能是因为之前做过这题，感觉有点像吧。

不得不说，发明反悔贪心的人绝对是个天才。

建议之前没有做过反悔贪心的可以去看看这题，因为这个东西确实很奇妙，第一次接触可能不太好理解。

反悔贪心，顾名思义就是说在贪心的过程中可以进行撤回之前某一步操作，这也使得这个算法应用场景并不是很多，因为绝大多题目是很难进行撤回操作的，而且这个算法套路性也比较强。

一般撤回操作要和贪心操作是类似的，这样子我们直接进行贪心过程就可以不用考虑哪几步要贪心，哪几步要撤回，一直做下去就是最优的。常用数据结构就是堆（这里也叫做反悔堆）和链表（支持快速插入删除元素）等，其实直接用 set 代替好像更方便点吧。

至于哪些题可以使用反悔贪心，还需要多刷题找感觉。不过有一类题目大概率可以用反悔贪心，就是只贪心一步是好想的，可能会分几类，然后之后就很复杂，但是撤回操作也是好想的，也就是说可以找到一个等价的东西把第一步换回来，且所耗费的代价与操作的代价相等，或者说可以在第一步分的某一类里找到与第一步相反的操作。可能觉得云里雾里？看看在这题怎么体现的。

回到本题，一个比较显然的贪心就是对于一大段正数或者一大段负数肯定要么一起选，要么一起都不选。原因就是如果一大段正数不选完，那么选完它会更优；而如果一大段负数不选完，那么不选它一定更优，其实选负数是为了把与它相邻的两正数段合并在一起，所以这种情况下一定要把这个负数段全部选完更优（不然正数段无法合并在一起）。所以我们可以把所有连续的正数合并在一起，所有连续的负数合并在一起。接下来的叙述都是建立在合并完的序列上，也就是序列里正数与负数交替出现，将这个序列记为 a。

想到这里好像没啥思路了，但是可以发现如果记正数个数为 p，那么若 p\le m，则把所有正数选完一定最优。

而如果 p>m，那么我们可以理解为把正数全部选完再撤回一些操作。发现此时撤回一步操作是好实现的，可以直接贪心，也就是说当 p=m+1 的时候，我们可以选择直接删除一个最小正数（定义其为第一类操作），或者合并一个最大负数两边的正数（连同这个负数一起）（定义其为第二类操作）。这就符合上文说的“只贪心一步是好想的，可能会分几类”，此处分了两类。

若记所有正数和为 S，假设最小的正数为 a_i，最大的负数为 a_j，那么第一类操作会使得答案变为 S-a_i，第二类操作会使得答案变为 S+a_j。乍一看两者没啥联系，一个取最小值，一个取最大值，一个是加号，一个是减号，但是请不要忘记一个是正数一个是负数。我们会惊讶的发现，对两者取绝对值之后竟然变统一了，即都是取最小的绝对值进行更新，并且更新之后的值 S-|a_i| 与 S-|a_j| 形式上完全统一，所以我们可以按照 a 中的绝对值进行排序，每次取出最小的元素来更新答案即可。但是按照此方法一直贪心肯定有问题，因为每次操作都会使得 a 序列发生改变而对后续操作产生影响，不再可以贪心，并且情况会越来越复杂。

此时我们可以考虑撤回操作了，对于第一类操作，撤回的意义在于 a_i 与其他正数合并比直接删除它更优，而这样的合并不会发生在只与其某一边相邻的正数合并（此处相邻指忽略负数之后的相邻），一定是跨过其两侧相邻正数的区间，也就是说与 a_i 合并的数要同时包含 a_{i-2} 和 a_{i+2}。以左边为例，如果最优解只包含 a_{i-2} 那么此次操作与直接对 a_{i-1} 进行第二类操作是等价的，而根据贪心，既然之前没有进行这样子的操作说明其不够优秀，故在此处它也不优秀。右边同理。所以回撤之后 a_{i-1} 与 a_{i+1} 要么同时被选，要么同时不被选（同时选表示 a_i 与 a_{i-2} 与 a_{i+2} 合并，即撤回操作，不同时选表示不撤回，保留第一类操作）。

那么我们可以每次进行操作一之后把其两侧的负数 a_{i-1} 与 a_{i+1} 合并在一起，也就是添加一个价值为 a_i+a_{i-1}+a_{i+1} 的元素，并把这两个负数从原序列删去。由于此时 a_{i-1} 和 a_{i+1} 的绝对值要大于 a_i（否则之前就会对 a_{i-1} 和 a_{i+1} 其中之一进行第二类操作，从而删除 a_i），那么 a_i+a_{i-1}+a_{i+1} 就是一个负数。如果我们某一次操作选择这个合并元素，即对 a_i+a_{i-1}+a_{i+1} 进行第二类操作（满足上文所述“可以在第一步分的某一类里找到与第一步相反的操作”），答案就会变为 S-|a_i+a_{i-1}+a_{i+1}|=S+a_i+a_{i-1}+a_{i+1}，而之前对 a_i 进行了第一类操作，也就是说此时的 S 已经减去了 |a_i|，这样子总体答案就增加了 a_{i-1}+a_{i+1}，即减去了 |a_{i-1}|+|a_{i+1}|，这与直接合并 a_{i-2} a_{i-1} a_i a_{i+1} a_{i+2} 的答案是等价的。而更巧妙的是我们删除了两个元素，而且正好进行了两次操作（对 a_i 进行第一类操作和对 a_{i-1}+a_i+a_{i+1} 进行反悔操作），满足上文所述“可以找到一个等价的东西把第一步换回来，且所耗费的代价与操作的代价相等”，这样子，每一次第一类操作都可以通过一个第二类操作等效回来，保证了反悔贪心的正确性。

对于第二类操作的撤回操作是同理的。可以证明每一个进行操作的 a_j，a_{j-1} 和 a_{j+1} 一定同时被选或者同时不被选，证明原理是类似的，留给读者思考。而我们也可以类比上面的方法，每次对 a_j 进行一次第二类操作，我们就把 a_{j-1}+a_j+a_{j+1} 当成一个新元素，并且删除 a_{j-1} 与 a_{j+1}，而由于 a_{j-1}+a_j+a_{j+1} 一定为正数（此处证明同上），所以某次如果选择这个元素，即对 a_{j-1}+a_j+a_{j+1} 进行第一类操作，那么答案就会变为 S-|a_j+a_{j-1}+a_{j+1}|=S-a_j-a_{j-1}-a_{j+1}，同理这里的 S 在之前对 a_j 进行第二类操作时已经减少了 |a_j| 即增加了 a_j，此时整体答案减少 a_{j-1}+a_{j+1} 与直接删除 a_{j-1} 和 a_{j+1} 是等价的，且操作次数与删除元素个数相等均为二。

至此，反悔贪心的证明就全部结束，希望这大段证明能对大家有帮助。

代码实现

有几处细节需要说明，首先对于原序列中的 0，可以直接删去不影响答案。其次对于每次对序列两端的元素进行，如果值为负，那么直接跳过不会对答案产生贡献，因为选负数是为了连接两端正数，而某一侧没有正数所以不选它一定更优。但是这个特判不可以在贪心之前直接删除两端的负数，因为之后会对 a 序列进行若干次修改使得其中元素值的正负发生变化，所以这个判断只能便贪心边进行。

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef pair<int,int> PII;
const int N=1e5+10;
int n,m,a[N],b[N],cnt,ans;
int pre[N],nxt[N];//链表
bool vis[N];
priority_queue<PII,vector<PII>,greater<PII> > q;//小根反悔堆，这里用set也可以

void Del(int x)//删除操作
{
    if(x<1||x>n) return;//因为堆里面特判了，所以这行删去也可以A
    vis[x]=1;//堆的懒惰删除法，和Dijkstra的删除原理差不多
    nxt[pre[x]]=nxt[x];
    pre[nxt[x]]=pre[x];
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
    {
        if(!a[i]) continue;
        if(i==1||(long long)a[i]*b[cnt]<0) b[++cnt]=a[i];//这里a[i]*b[cnt]不可以写成a[i]*a[i-1]，因为可能a[i-1]是0，就会挂
        else b[cnt]+=a[i];
    }//b中存储的是合并后的值
    n=cnt;cnt=0;
    for(int i=1;i<=n;i++) a[i]=b[i];
    for(int i=1;i<=n;i++)//堆和链表初始化
    {
        pre[i]=i-1,nxt[i]=i+1;
        q.push(make_pair(abs(a[i]),i));
        if(a[i]>0) ans+=a[i],cnt++;
    }
    while(cnt>m)
    {
        PII u=q.top();q.pop();
        if(vis[u.se]) continue;
        if((pre[u.se]>=1&&nxt[u.se]<=n)||a[u.se]>0)//边界处的负数直接不用管，这个不可以在贪心之前直接判掉
        {
            ans-=u.fi;cnt--;
            a[u.se]+=a[pre[u.se]]+a[nxt[u.se]];
            q.push(make_pair(abs(a[u.se]),u.se));//这里记得加上绝对值
            Del(pre[u.se]);Del(nxt[u.se]);//删除左右节点
        }
    }
    printf("%d\n",ans);
    return 0;
}