反悔贪心和例题

反悔贪心

什么是反悔贪心：

• 我们都知道贪心就是把局部最优解作为整体最优解，然后一步步的迭代，直到找到全局最优解的过程。但是有些时候，贪心策略可能并不是正解，局部的最优解可能不是全局的最优解。
• 反悔贪心顾名思义就是带反悔的贪心。我们先找到局部的最优解，如果枚举到后面，发现之前选取的不是最优解，那么我们要做一个反悔操作，修改之前的局部最优解。但这个修改并不是真的改掉之前的操作，而是在之前局部最优解的基础上进行修改，达到反悔的效果。

例题1：CF865D

您可以完美预测某只股票未来 $N$ 天的价格。每天你要么买入一股，要么卖出一股，要么什么都不做。起初你拥有零股，当你没有任何股票时，你不能卖出股票。在 $N$ 天结束时，您希望再次拥有零股，但希望拥有尽可能多的资金。

• 正解一定是买便宜的再买贵的，遍历所有股票，如果在这张股票之前有比它便宜的，肯定是在便宜的一天买，在贵的一天卖。可以用小根堆维护前面最便宜的数字。
• 但是有一组数据 1,2,100可以卡掉这个贪心，如果在第二天发现第一天便宜，就在第一天买，第二天卖，那么第三天就没有股票卖了。策略显然是先买 $1$，后卖 $100$。
• 这时贪心不是局部最优解，我们考虑可不可以进行反悔操作。首先在第二天时，$sum+=a[2]-a[1]$，在遍历的过程中发现 $100$ 显然更优。那么这时如果要反悔,不卖掉 $a[2]$，去卖掉 $a[3]$。有 $sum+=a[3]-a[2]$。这个过程，跟买了 $a[2]$，卖掉 $a[3]$ 的过程很相似，唯一的区别就是在这之前已经有了一步 $sum+=a[2]-a[1]$。这时如果物品 $a[3]$ 选取了 $a[2]$ ，就达到了 $sum=a[3]-a[1]$ 的效果。
• 大概流程就是，如果某一天 $a[j]$ 发现前面一天比它便宜，就在小根堆里面把 $a[i]$ 弹出，更新 $sum$ 的值。弹出的物品就是买的股票，然后放入两次 $a[j]$，第一次代表正常贪心购买 $a[j]$。第二次代表反悔操作，把 $a[i]$ 卖掉，然后重新放回 $a[j]$。
• 每次反悔操作不会导致某一天进行了买入又卖出的操作，因为如果反悔，卖出的一定是当前这一天。
• 代码如下：

  // LUOGU_RID: 166565189
  #include <bits/stdc++.h>
  using namespace std;
  #define int long long
  #define inf 0x3f3f3f3f3f3f3f3f
  const int N=1e6+10;
  const int mod=1e9+7;
  int a[N];
  signed main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n;cin>>n;priority_queue<int,vector<int>,greater<int>> q;int sum=0;for(int i=1;i<=n;i++){int x;cin>>x;if(q.empty()||q.top()>=x){q.push(x);}else{sum+=x-q.top();q.pop();q.push(x);q.push(x);}}cout<<sum<<endl;return 0;
  }
  

例题2：Luogu P1484 种树

cyrcyr 今天在种树，他在一条直线上挖了 $n$ 个坑。这 $n$ 个坑都可以种树，但为了保证每一棵树都有充足的养料，cyrcyr 不会在相邻的两个坑中种树。而且由于 cyrcyr 的树种不够，他至多会种 $k$ 棵树。假设 cyrcyr 有某种神能力，能预知自己在某个坑种树的获利会是多少（可能为负），请你帮助他计算出他的最大获利。

• 题意简单来说，是给定 $n$ 个数，选取不能两两相邻的 $k$ 个数，求最大和。
• 我们先不考虑 $k$ 个数字的限制，如果都是正数，那么我们选取的串一定是0101010或1010101两种情况。
• 再考虑 $k$ 很小的情况，我们发现，如果 $k=1$，选取的一定是价值最大的坑，如果 $k=2$ ，设最大数为 $x$， 选取的要么是 $x$ 和扣掉 $x$ 相邻两个数剩下区间的最大数，要么就是选取 $x$ 相邻两个数，不会出现只选取相邻一个数的情况，因为这样选取 $x$, 一定比选相邻数更优。
• 加上 $k$ 的限制之后，我们选取的 $01$ 串应该变成什么样呢？它一定是某些 $01$ 交替串和一些 $0$ 的连接
• 考虑反悔贪心，如果选取串 $1$ ，向后遍历，如果 $101$ 比 $1$ 更优，就应该把101换成1，同理，如果 $10101$ 比 $101$ 更优，也要把它放进去。推一遍式子:
• $v[1]=a[3],v[101]=a[2]+a[4],v[10101]=a[1]+a[3]+a[5]$
• $v[101]=v[1]+a[2]+a[4]-a[3],v[10101]=v[101]+a[1]+a[5]-(a[2]+a[4]-a[3])$
• 可以发现，如果将 $ f_子=a[l]+a[r]-v[子串] $ 放入，那么$ v[父串]=v[子串]+f_子 $ 所以每次只需要把 $f_子 放入，就可以反悔。
• 用双向链表维护 $l$ 和 $r$，由于每次反悔只增加一个，跟选取元素差不多。跟例题1类似。大根堆维护就行了
• 代码如下：

  #include <bits/stdc++.h>
  using namespace std;
  #define int long long
  #define inf 0x3f3f3f3f3f3f3f3f
  #define pii pair<int, int>
  #define endl '\n'
  const int N=3e5+10;
  const int mod=1e9+7;
  int a[N],vis[N];
  map<int, int> l,r;
  priority_queue<pii> q;
  signed main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n,k;cin>>n>>k;for(int i=1;i<=n;i++){cin>>a[i];l[i]=i-1;r[i]=i+1;q.push(make_pair(a[i],i));}int sum=0;for(int i=1;i<=k;i++){while(!q.empty()&&vis[q.top().second]) q.pop();pii now=q.top();q.pop();if(now.first<=0) break;sum+=now.first;vis[l[now.second]]=vis[r[now.second]]=1;now.first=a[now.second]=a[l[now.second]]+a[r[now.second]]-now.first;q.push(now);l[now.second]=l[l[now.second]];r[now.second]=r[r[now.second]];r[l[now.second]]=l[r[now.second]]=now.second;}cout<<sum<<endl;return 0;
  }