2017-08-02 14:27:18
writer：pprp
题意：
• 每块木板宽度均为1，高度为h[i]
• n块木板连接为宽度为n的栅栏
• 每次可以刷一横或一竖(上色)
• 最少刷多少次可以使得栅栏被全部上色
• 1 ≤ n ≤ 5000
算法分析：可以横着刷，可以竖着刷，横着刷是为了减小竖着刷的次数
采用分治，每个分治中都取横着刷和竖着刷两者的最小值
代码及说明如下：
#include <iostream>
#include <queue> using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = ;
int n;
int a[maxn]; //在递归算法中不要用n，应该考虑的是在每个部分，而不能只是在第一个递归中的角标
int dfs(int l,int r)
{
int MIN = INF;
int cnt = ; //找到所有木板中最短的那个
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] == )
{
cnt +=dfs(left,i-);
left = i+ ;
}
} //最后一段,需要一个判断
if(left <= r)
cnt += dfs(left,r); return min(cnt,r-l+);
} int main()
{
cin >> n; for(int i = ; i <= n ; i++)
{
cin >> a[i];
} cout << dfs(,n) << endl; return ;
}