2017-08-02 14:27:18

writer：pprp

题意：

　　• 每块木板宽度均为1，高度为h[i]

　　• n块木板连接为宽度为n的栅栏

　　• 每次可以刷一横或一竖(上色)

　　• 最少刷多少次可以使得栅栏被全部上色

　　• 1 ≤ n ≤ 5000

算法分析：可以横着刷，可以竖着刷，横着刷是为了减小竖着刷的次数

　　　　采用分治，每个分治中都取横着刷和竖着刷两者的最小值

---

 

代码及说明如下：

#include 
     
      #include 
      
       using namespace std;const int INF = 0x3f3f3f3f;const int maxn = 5010;int n;int a[maxn];//在递归算法中不要用n，应该考虑的是在每个部分，而不能只是在第一个递归中的角标int dfs(int l,int r){    int MIN = INF;    int cnt = 0;    //找到所有木板中最短的那个    for(int i = l ; i <= r; i++)    {        MIN = min(MIN, a[i]);    }    //将数目加上最短板长度    cnt += MIN;    //所有的木板减去这个长度    for(int i = l; i <= r; i++)    {        a[i] -= MIN;    }    int left = l;    //  分段递归解决问题    for(int i = l; i <= r; i++)    {        if(a[i] == 0)        {            cnt +=dfs(left,i-1);            left = i+1 ;        }    }        //最后一段,需要一个判断    if(left <= r)        cnt += dfs(left,r);    return min(cnt,r-l+1);}int main(){         cin >> n;        for(int i = 1 ; i <= n ; i++)    {        cin >> a[i];    }        cout << dfs(1,n) << endl;    return 0;}