#C240222B. 染色

前言（Front talk)

$\qquad$根本就没有往分治这方面想呢~考点又多了一个。

网址（Website）

$\qquad$ 题目详情 - 染色 - Super

$\qquad$ 题解 - 染色 - Super

题解（Solution）

$\qquad$容易发现，对于操作二，当且仅当至少染色了当前方块堆中最小的那一堆才有可能比操作一更优。

$\qquad$对于 $40pts$ ，我们直接全部用操作一，因为操作二每次最多消除当前所有的最小方块堆，因为 $a_i$ 互不相同，每次操作二就最多消除一堆方块（甚至还有可能多做几次，因为一次只能消一层），所以不如直接操作一将每一个打完，输出 $n$。

$\qquad$剩下的 $60pts$ 呢？既然操作二必须消除当前最小的那一堆，我们每次就找到当前的最小值，计算将最小值消除需要的操作数，与一个一个打进行比较。去掉最小值后，当前的方块堆会分为若干个小堆，再继续在那些小堆里面重复进行操作。容易看出，当前的任务分成了若干个子任务。

$\qquad$因此想到了分治。临界就是当 $l==r$ 时，返回 $1$ ；当 $l>r$ 时，返回 $0$ 。

代码（Code）

#include<bits/stdc++.h>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int> 
#define int long long
inline int input(){int x;return cin>>x,x;}
const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 5005; 

int n,ans,a[N];

inline int Solve(int l,int r,int h){
	if(l==r) return a[l]!=h;
	if(l>r) return 0;
	int minn=inf, pos = 0;
	For(i,l,r) if(minn > a[i]) minn = a[i], pos = i;
	int res = min(Solve(l,pos-1,minn)+Solve(pos+1,r,minn)+a[pos]-h, r-l+1);
	return res;
}

signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	string str("paint");
	freopen((str+".in").c_str(),"r",stdin);
	freopen((str+".out").c_str(),"w",stdout);
	cin>>n;For(i,1,n) a[i]=input();
	int Tim = clock();
	cout<<Solve(1,n,0)<<'\n';
	return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}