CF1400E Clear the Multiset
一道经典简单的分治
由贪心可知，对于一段区间[L,R]，一共有两种处理方式
1.一个一个减，次数为l-r+1
2.先区间减，直到最小的减没了，在考虑最小值隔开的两个区间。如果有多个最小值，其实也不影响，再往下分的时候一定会分开。区间答案就是 $min(l-r+1,f(l,p-1)+f(p+1,r)+minn)$ 具体含义见代码
#include<bits/stdc++.h> using namespace std; const int N=5e5+5; int a[N],n; int work(int l,int r){ if(l>r) return 0; if(l==r) return min(a[l],1); int minn=2e9+555,p; for(int i=l;i<=r;i++){ if(minn>a[i]){ minn=a[i];p=i; } } for(int i=l;i<=r;i++) a[i]-=minn; return min(r-l+1,work(l,p-1)+work(p+1,r)+minn); } int main(){ cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; cout<<work(1,n); return 0; }