http://codeforces.com/problemset/problem/448/C
题目大意：给你一个栅栏，每次选一横排或竖排染色，求把全部染色的最少次数，一个点不能重复染色。
和这道题有点像，不过可以竖着。
考虑横着涂一次的情况,那么有两个显而易见的事实。
1.这次涂色长度必须尽可能大。
2.在这次涂色区域的下方,必定都是横着涂的。
所以,对于一串栅栏h 1 , h 2 , ... , h n ,如果要横着涂,就必定要从底向上涂min{h 1 , h 2 , ... , h n }次。这样以后,h 1 , h 2 , ... , h n 就会分成若干不连通的子局面。
那么显然可以设计一个分治的算法,时间复杂度为O(N 2 ):
令\(Solve(l, r, h)\)代表\([l, r]\)这段栅栏,已经从下向上涂了h格的答案。
令 \(h'= min{h_1, h_2 , ... , h_n }\),那么:
\(Solve(l, r, h) = min{r - l + 1, \sum solve(u, v, h')|[u, v]为分割出的子局面}\)
边界情况:l = r 时,答案显然为 1。
以后static不能乱用（在递归中），，，
// It is made by XZZ
#include<cstdio>
#include<algorithm>
#define Fname "color"
using namespace std;
#define rep(a,b,c) for(rg int a=b;a<=c;a++)
#define drep(a,b,c) for(rg int a=b;a>=c;a--)
#define erep(a,b) for(rg int a=fir[b];a;a=nxt[a])
#define il inline
#define rg register
#define vd void
typedef long long ll;
il ll gi(){
rg ll x=0;bool flg=0;rg char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')flg=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return flg?-x:x;
}
ll n,h[5010];
il ll Doit(ll l,ll r,ll _h){
if(l==r)return 1;
ll m=2e18;
rep(i,l,r)m=min(m,h[i]);
ll ans=m-_h;
rep(i,l,r)
if(h[i]!=m){
ll j;j=i;
while(j!=r&&h[j+1]!=m)++j;
ans+=Doit(i,j,m),i=j+1;
}
return min(ans,r-l+1);
}
int main(){
freopen(Fname".in","r",stdin);
freopen(Fname".out","w",stdout);
n=gi();
rep(i,1,n)h[i]=gi();
printf("%lld\n",Doit(1,n,0));
return 0;
}