painting fence - 分治 - Codeforces 448c

湛蓝之海

2017-08-02 14:27:18
writer：pprp
题意：
· 每块木板宽度均为1，高度为h
· n块木板连接为宽度为n的栅栏
· 每次可以刷一横或一竖(上色)
· 最少刷多少次可以使得栅栏被全部上色
· 1 ≤ n ≤ 5000
算法分析：可以横着刷，可以竖着刷，横着刷是为了减小竖着刷的次数
采用分治，每个分治中都取横着刷和竖着刷两者的最小值
代码及说明如下：

#include <iostream>
#include <queue>
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;
}

代码改变世界