永远无法理解的题
分治
单调栈 笛卡尔树
1 #include<iostream>
2 #include<algorithm>
3 #include<cmath>
4 #include<stack>
5 #include<cstring>
6 using namespace std;
7 const int N = 5e3 + 10;
8 int n;
9 int a[N];
10 int ch[N][2];
11 int sz[N];//操作次数
12
13 int read(){
14 char k = getchar(); int x = 0;
15 while(k < '0' || k > '9') k = getchar();
16 while(k >= '0' && k <= '9') x = x * 10 + k - '0' ,k = getchar();
17 return x;
18 }
19
20 inline int div_con(int now, int x)
21 {
22 if(now == 0) return 0;
23 int l = div_con(ch[now][0], now), r = div_con(ch[now][1], now);
24 sz[now] = 1 + sz[ch[now][0]] + sz[ch[now][1]];
25 return min(sz[now], l + r + a[now] - a[x]);
26 }
27
28 int main(){
29 n = read();
30 stack<int> s;while(!s.empty()) s.pop();
31 for(int i = 1 ; i <= n ; i++){
32 a[i] = read();
33 if(s.empty() || a[s.top()] < a[i]){
34 s.push(i);//推进去的是编号哦
35 }else{
36 int last = 0;//最后一个大于等于它的值的编号
37 while(!s.empty() && a[s.top()] >= a[i]){
38 last = s.top();s.pop();
39 if(!s.empty() && a[s.top()] >= a[i]){
40 ch[s.top()][1] = last;
41 }
42 }
43 ch[i][0] = last;
44 s.push(i);
45 }
46 }
47 int root = 0;//当前序列中最小的值
48 while(!s.empty()){
49 root = s.top();s.pop();
50 if(!s.empty()){
51 ch[s.top()][1] = root;
52 }
53 }
54 printf("%d
", div_con(root, 0));
55
56 return 0;
57 }