反悔贪心小记

额这个东西也是高中觉得挺难的，一直没有真正理解内涵，现在又做了道题后觉得真的还好，还是没有理解原理导致的。那就简单记录一下吧。

例：低谷

在给定长度为 \(n\) 的数组中，通过最多进行 \(k\) 次任意元素减一操作，求操作后数组中可能出现的最大低谷数。对于数组 \(a\)，位置 \(i\) 是低谷当且仅当 \(2\leq i\leq n-1\) 且满足 \(a_i<a_{i-1}\) 和 \(a_i<a_{i+1}\)。

显然，将位置 \(i\) 转化为低谷的花费为 \(\max(0,a_i-\min(a_{i-1},a_{i+1})+1)\)。一共有 \(n-2\) 个位置可以转化为低谷，然后低谷之间不能相邻。这个问题就转化为了：

求相邻的元素不能同时取，且总和小于等于 \(k\) 的情况下，能取的元素的最大个数。

既然是贪心，我们就肯定先取花费最小的位置，假设为 \(loc\)，并获得 \(1\) 个低谷。同时取完之后这个位置两侧的数就不能再取了。

但是由于我们需要考虑整体，因此可能后面会取到 \(loc+1\) 和 \(loc-1\) 的数，同时放弃 \(loc\) 位置的数。同时取完之后 \(loc+2\) 和 \(loc-2\) 位置的数不能再取了。

然后我们就可以发现，进行一次这样反悔操作，相当于花费了 \(a_{loc+1}+a_{loc-1}-a_{loc}\) 的代价，多获得了 \(1\) 个低谷，同时 \(a_{loc+2}\) 和 \(a_{loc-2}\) 不能再选。于是乎，当我们选 \(loc\) 的时候，我们就考虑到未来可能会进行的反悔操作，删掉，并将这个反悔操作抽象为和取数一样的操作。即，我们删去 \(a_{loc-1}\) 和 \(a_{loc+1}\) 和 \(a_{loc}\)，在原 \(loc\) 位置新增一个数 \(a_{loc}'=a_{loc+1}+a_{loc-1}-a_{loc}\) ，并将其与 \(a_{loc-2}\) 和 \(a_{loc+2}\) 挨着。这样我们先取 \(a_{loc}\) 再进行取 \(a_{loc}'\) 的实质就是取 \(a_{loc-1}\) 和 \(a_{loc+1}\)，然后 \(a_{loc+2},a_{loc},a_{loc-2}\) 目前不能选择。一直进行这样的过程。容易发现每次取一次数代价都是最优的，且能多得到一个低谷同时不会忽视所有潜在情况。

最后，这个过程可以使用链表和优先队列实现，完了。

const int N=200005;
int n,pre[N],nxt[N],del[N];ll k,a[N],val[N];
inline ll cost(ll loc){
	ll c1=max(a[loc]-a[loc-1]+1,0ll);
	ll c2=max(a[loc]-a[loc+1]+1,0ll);
	return max(c1,c2);
}
int main(){
	scanf("%d%lld",&n,&k);
	for(int i=1;i<=n;++i){
		scanf("%lld",&a[i]);
	}
	priority_queue<ttfa,vector<ttfa>,greater<ttfa>>q;
	for(int i=2;i<n;++i){
		pre[i]=i-1,nxt[i]=i+1;
		val[i]=cost(i);
		q.push({val[i],i});
	}val[1]=val[n]=k+k;
	pre[1]=1,nxt[1]=2;
	nxt[n]=n,pre[n]=n-1;
	ll sum=0,ans=0;
	while(!q.empty()){
		int loc=q.top().second;q.pop();
		if(del[loc])continue;
		if(val[loc]+sum>k)break;
		sum+=val[loc];++ans;
		val[loc]=val[pre[loc]]+val[nxt[loc]]-val[loc];
		del[pre[loc]]=del[nxt[loc]]=1;
		nxt[pre[pre[loc]]]=loc;
		pre[nxt[nxt[loc]]]=loc;
		pre[loc]=pre[pre[loc]];
		nxt[loc]=nxt[nxt[loc]];
		q.push({val[loc],loc});
	}
	printf("%lld\n",ans);
	return 0;
}

对于 \(n\leq 2000\) 的规模，可以使用 \(O(n^2)\) 的 DP，定义 \(f_{i,j}\) 为前 \(i\) 个数构成 \(j\) 个低谷的最少花费，转移较为朴素，最后枚举 \(f_n\) 即可。但是当 \(n\) 较大时，则只能考虑使用反悔贪心求解。

然后再附一下 \(O(n^2)\) DP 的代码，记得赛后在牛客上看了下这个题，当时写了个 DP 出了一堆锅，感觉还是要先自己想好转移和初始态，这回就一遍写过了。

int main(){
	scanf("%d%lld",&n,&k);
	for(int i=1;i<=n;++i)scanf("%lld",&a[i]);
	memset(dp,0x3f,sizeof(dp));
	dp[0][0]=dp[1][0]=dp[2][0]=0;
	for(int i=3;i<=n;++i){
		dp[i][0]=0;
		for(int j=1;j<=n/2;++j){
			dp[i][j]=min(dp[i-1][j],dp[i-2][j-1]+cost(i-1));
		}
	}
	for(int j=n/2;j>=0;--j)
		if(dp[n][j]<=k)return printf("%d\n",j),0;
	puts("-1");
	return 0;
}

另一道典：LG1484 种树

\(n\) 个位置，第 \(i\) 个位置可以得到 \(a_i\) 的收益，最多取 \(k\) 个位置且取的位置不能相邻，问能取得的最大收益。

只不过是改了下限制条件，从收益变成了位置，其他是一样的。