CodeForces 448C Painting Fence

 1     #include<iostream>
 2     #include<algorithm>
 3     #include<set>
 4     #include<cstdio>
 5     #include<cstdlib>
 6     #include<cmath>
 7     using namespace std;
 8     #define FOR(i,j,k) for(int i=j;i<=k;i++)
 9     #define FORD(i,j,k) for(int i=j;i>=k;i--)
10     #define LL long long
11     #define SZ(x) int(x.size())
12     #define maxn 5010
13     int n;
14     int a[maxn];
15     int fz(int l,int r,int v)
16     {
17         if(l<=r)
18         {
19         /*int ss=999999;
20         int s=0;
21         FOR(i,l,r)
22         if(a[i]<ss) {ss=a[i];s=i;}
23         return min(r-l+1,fz(l,s-1,ss)+fz(s+1,r,ss)+ss-v);*/
24         int m=min_element(a+l,a+r+1)-a;
25         return min(r-l+1,fz(l,m-1,a[m])+fz(m+1,r,a[m])+a[m]-v);
26         }
27         else return 0;
28     }
29     
30     int main()
31     {
32     cin>>n;
33     FOR(i,1,n)
34     cin>>a[i];
35     cout<<fz(1,n,0);
36     return 0;
37     }
38