首页 > 其他 > 详细

【题解】 CF1400E Clear the Multiset 笛卡尔树+贪心+dp

时间:2020-09-21 23:44:36      阅读:136      评论:0      收藏:0      [点我收藏+]

Legend

Link \(\textrm{to Codeforces}\)

给定长度 \(n\ (1 \le n \le 5000)\) 的自然数数组,你每次可以进行如下操作:

  • 给一个区间的数 -1,前提是这个区间没有 0;
  • 给某一个位置上的数减去任意正整数,但操作后值不能小于 0。

求出使得所有数字变成 0 的最少操作次数。

Editorial

不是很理解为什么 \(O(n)\) 的题目要出成 \(n=5000\)

如果只有操作 \(1\),那么就是铺设道路/积木大赛。不过根据这两个经典题我们可以知道:如果要用操作 \(1\),一定会贪心地把一个数字减成 \(0\)

那么这个不幸被减成 \(0\) 的数字是什么呢?显然是区间最小值。

\(O(n^2)\) 做法呼之欲出:每次要么区间全部都用操作 2 干掉,要么先把最小值减掉递归成若干个子区间。

用可以区间查询最小值的数据结构随便维护维护就可以做到 \(O(n \log n)\) 了。

而这个维护最小值的数据结构也可以是笛卡尔树,它正好是区间分裂的位置,方便统计区间大小和递归左右子树,可以 \(O(n)\) 解决这个问题。

Code

为了写这个题口糊了一下怎么写笛卡尔树,没想到竟然是对的(

#include <bits/stdc++.h>

using namespace std;

int read(){
	char k = getchar(); int x = 0;
	while(k < ‘0‘ || k > ‘9‘) k = getchar();
	while(k >= ‘0‘ && k <= ‘9‘) x = x * 10 + k - ‘0‘ ,k = getchar();
	return x;
}

const int MX = 5000 + 23;
int a[MX] ,ch[MX][2];

stack<int> stk;

int size[MX];

int dapai(int x ,int f){
	if(x == 0) return 0;
	int l = dapai(ch[x][0] ,x) ,r = dapai(ch[x][1] ,x);
	size[x] = 1 + size[ch[x][0]] + size[ch[x][1]];
	int Ans = min(l + r + a[x] - a[f] ,size[x]);
	return Ans;
}

int main(){
	int n = read();
	for(int i = 1 ; i <= n ; ++i){
		a[i] = read();
		if(stk.empty() || a[stk.top()] < a[i]){
			stk.push(i);
		}else{
			int las = 0;
			while(!stk.empty() && a[stk.top()] >= a[i]){
				las = stk.top(); stk.pop();
				if(!stk.empty() && a[stk.top()] >= a[i]){
					ch[stk.top()][1] = las;
				}
			}
			ch[i][0] = las;
			stk.push(i);
		}
	}
	int root = 0;
	while(!stk.empty()){
		root = stk.top();
		stk.pop();
		if(!stk.empty()){
			ch[stk.top()][1] = root;
		}
	}
	cout << dapai(root ,0) << endl;
	return 0;
}

【题解】 CF1400E Clear the Multiset 笛卡尔树+贪心+dp

原文:https://www.cnblogs.com/imakf/p/13709163.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!