传送门

Description
zed 最近总是受到 Farmer 的困扰,因此他在自家的门前插了一排栅栏以防农气的入侵。栅栏由 N 个竖条栅栏横向组成,每个竖条栅栏宽度为 1。
过了一段时间,zed 觉得栅栏非常不美观。因此,他想给栅栏涂上颜色。问题是,zed的刷子宽度只有 1,也就是说,一次只能将连续的一排或一列格子涂上颜色(长度任意)。
zed 想用最少的次数把栅栏全部涂上颜色(注意,一个格子不能重复涂色)。但是 zed 现在没时间,所以这个问题就交给你了。

Input
第一行为一个整数 N,代表栅栏的宽度。
第二行为 N 个整数 h 1 ~ h n ,代表从左向右每个竖条栅栏的高度。

Output
输出文件有且仅有一行,一个整数 ans,代表将整个栅栏涂色所用最少次数。

Solution:

" 　考虑横着涂一次的情况,那么有两个显而易见的事实。
　　1、 这次涂色长度必须尽可能大。
　　2、 在这次涂色区域的下方,必定都是横着涂的。
　　所以,对于一串栅栏h1,h2,...,hn,如果要横着涂,就必定要从底向上涂min⁡{h1,h2,...,hn}次。

　　这样以后,h1,h2,...,hn就会分成若干不连通的子局面。
　　那么显然可以设计一个分治的算法,时间复杂度为O(N²):
　　令Solve(l, r, h)代表[l, r]这段栅栏,已经从下向上涂了h格的答案。
　　令 h′=min⁡{h1,h2,...,hn},那么:
　　Solve(l,r,h)=⁡min{⁡r−l+1,∑solve(u,v, h ′ )⁡|⁡[u, v]为分割出的子局面⁡⁡}
　　边界情况:l=r时,答案显然为1。  "

CODE:

 #include<iostream>

 #include<cstdio>

 #define R register

 #define go(i,a,b) for(R int i=a;i<=b;i++)

 #define M 5000+1

 #define inf 2100000000

 using namespace std;

 int read()

 {

     int x=,y=;;char c=getchar();

     while(c<''||c>'') {if(c=='-') y=-;c=getchar();}

     while(c>=''&&c<='') {x=(x<<)+(x<<)+c-'';c=getchar();}

     return x*y;

 }

 int n,h[M];

 int solve(int l,int r,int h1)

 {

     if(l>r) return ;

     int minh=inf,ans,l1=l;

     go(i,l,r) minh=min(minh,h[i]);

     ans=minh-h1;

     go(i,l,r)

         if(h[i]==minh) ans+=solve(l1,i-,minh),l1=i+;

     ans+=solve(l1,r,minh);

     return min(ans,r-l+);

 }

 int main()

 {

     n=read();go(i,,n) h[i]=read();

     printf("%d",solve(,n,));

     return ;

 }