浅谈反悔贪心
lndjy
2020-10-05 08:09:38
### 引入
这是一篇普及选手也能看懂的讲解——就从普及的一道题，[纪念品](https://www.luogu.com.cn/problem/P5662)说起。
有人问，这不是一个 dp 吗？它确实是 dp，但是我要讲的是一个部分分做法。
当只有一种物品的时候，我们可以贪心。贪心策略是如果明天比今天高就今天买明天卖。那么万一后天或者大后天更高怎么办呢？明天再买回来。今天买->明天又卖又买->后天卖，就相当于今天买后天卖。
明天又买可以看成反悔了明天卖的，又持续到后天，这样，只要保证“今天卖->明天卖”的赚钱的每一步走好，答案就是最优的。这个“反悔”的过程就类似于反悔贪心。
### 反悔贪心的思想
反悔贪心的思想是既然这次不一定是最优，那么就先放着，如果以后找到更优的再取消这次操作，选取更优的操作。
这样的话只要保证当前最优就可以了，因为以后的更优会反悔。
维护当前最优和以后的反悔通常用堆实现。
不明白没关系，看下面的例题就明白了。
### 例题
本篇文章所有题都在[这个题单](https://www.luogu.com.cn/training/8793)里。
- [CF865D Buy Low Sell High](https://www.luogu.com.cn/problem/CF865D)
题意:已知接下来 $N$ 天的股票价格,每天你可以买进**一股**股票,卖出**一股**股票,或者什么也不做,求收益最大值。
做法：每天只能操作一次，所以我们要操作当前利益最大的。想让利益最大，那么就要让之前买的价格最低。那么就可以用一个小根堆来维护之前的最小值。每次取出最小的来操作。就相当于在那天买入在今天卖出。
但是这么做不一定最优，因为卖出时没有考虑后面的，这时就可以反悔了，当进行卖出操作时，把现在的价格再次放进堆里，这样当新的价值成为后面某个决策的最优点时，就可以反悔掉今天的卖出。
设 $c_i$ 表示 $i$ 天的价格，令 $i,j,k$ 分别为今天以前最优的买入天，今天，后面更优的决策天，那么利润是
$$(c_j-c_i)+(c_k-c_j)$$
化简得
$$c_k-c_i$$
这时发现反悔和直接在后面的天买是一样的。所以反悔的做法是正确的。其他同理，在接下来的题目讲解中就只提做法不证明了。
### 简单题
- [P2949 [USACO09OPEN]Work Scheduling G](https://www.luogu.com.cn/problem/P2949)
先按截止时间排序，然后用堆维护价值，堆里面的元素个数就是现在花费的时间。
当这个任务截止时间小于等于已经花的时间，如果当前价值比之前最小的价值高就反悔之前最小的价值采用今天的。
当这个任务截止时间大于等于已经花的时间，就先做了，不合算以后会反悔。
- [P4053 [JSOI2007]建筑抢修](https://www.luogu.com.cn/problem/P4053)
用一个变量维护现在的时间。当时间不够且这个任务更省时间（因为所有的价值相同），就改成现在的任务。时间够就先做着。
### 中等题
- [P1484 种树](https://www.luogu.com.cn/problem/P1484)
这道题的反悔不明显。正常操作是选择一个与已选的数不相邻的数。反悔操作是选择已选数左边和右边的。那么被选过的数反悔的价值是 `a[pre[now.id]].num+a[nxt[now.id]].num-now.num`。
`pre` 和 `nxt` 是一个双向链表。当前数被选中，那么左右的数就要删除。
代码：
```cpp
#include<iostream>
#include<queue>
#define int long long
using namespace std;
const int N=500005;
int pre[N],nxt[N],v[N];
int n,k,ans;
struct node
{
int num,id;
bool operator <(const node &p)
const{
return num<p.num;
}
}a[N];
priority_queue<node> q;
void del(int x)
{
nxt[pre[x]]=nxt[x];
pre[nxt[x]]=pre[x];
v[x]=1;
}
signed main()
{
cin>>n>>k;
if(k>n/2)
{
cout<<"Error!";
return 0;
}
for(int i=1;i<=n;i++)
{
cin>>a[i].num;
pre[i]=i-1;nxt[i]=i+1;
a[i].id=i;
q.push(a[i]);
}
nxt[0]=1;pre[n+1]=n;
for(int i=1;i<=k;i++)
{
while(v[q.top().id]) q.pop();
node now=q.top();q.pop();
if(now.num<=0)
{
cout<<ans;
return 0;
}
ans+=now.num;
now.num=a[pre[now.id]].num+a[nxt[now.id]].num-now.num;
q.push(now);
a[now.id]=now;
del(pre[now.id]);
del(nxt[now.id]);
}
cout<<ans;
return 0;
}
```
### 难题
- [CF436E Cardboard Box](https://www.luogu.com.cn/problem/CF436E)
这题难就难在贪心策略和反悔都有 2 种。
这题的直接选择有两种：
1. 花费 $a_i$ 加 1 星。
2. 花费 $b_i-a_i$ 由 1 星变为 2 星。
反悔也有两种：
1. 把一个一星反悔成不选，再找一个选两星,花费 $b_j-a_i$。
2. 把一个两星反悔成一星，再找一个选两星，花费 $b_j+a_i-b_i$。
这个东西一个堆是没有办法维护的，需要 5 个堆。
一个维护 $a_i$ ，一个维护 $b_i-a_i$，一个维护 $-a_i$，一个维护 $b_i$ ，一个维护 $a_i-b_i$ 。
然后按照反悔贪心的常规，4 种情况选择最小值即可。
### 挑战
- [P5470 [NOI2019]序列](https://www.luogu.com.cn/problem/P5470)
这应该是反悔贪心最难的题了，可以挑战一下。~~作为flag也是不错的选择~~