利用分治法求解果园篱笆问题

Question

1.利用分治法求解果园篱笆问题
问题描述：某大学ACM集训队，不久前向学校申请了一块空地，成为自己的果园。全体队员兴高采烈的策划方案，种植了大批果树，有梨树、
桃树、香蕉.....。后来，发现有些坏蛋，他们暗地里偷摘果园的果子，被ACM集训队队员发现了。因此，大家商量解决办法，有人提出：修筑一圈篱笆.把果园围起来，但是由于经费有限,必须尽量节省资金，所以，要找出一种最合
理的方案。由于每道篱笆，无论长度多长，单价都一样。所以，大家希望设
计出来的修筑一圈篱笆的方案所花费的资金最少。有人已经做了准备工序，统计了果园里果树的位置，每棵果树分别用二维坐标来表示。现在.他们要求根据所有的果树的位置，找出一个n边形的最小篱笆，使得所有果树都包围在篱笆内部，或者在篱笆边沿上。
设计算法，求出修筑一圈篱笆花费的资金最少的方案。

Answer 1

//保存各个木板高度的数组
vector<int>  h;
//返回h[left..right]区间中可截取的面积最大长方形的宽度。
int solve(int left, int right){
  // 初始部分:只有一个木板的情况
  if(left==right) return h[left];
  //分割为[left, mid]和[mid + 1, right]两个区间的子问题
  int mid = (left + mid) / 2;
  // 分别计算两个子问题。
  int ret = max(solve(left, mid), solve(mid + 1, right));
  // 子问题3：找出横跨两个子问题的面积最大的长方形
  int l0 = mid, hi = mid;
  int height = min(h[l0], h[hi]);
  //只考虑包含[mid, mid+1]的两个长方形
  ret = max(ret, height * 2);
  // 扩展长方形直到覆盖所有输入值。
  while(left< l0 || hi < right){
    // 总是向高度更高的方向扩展
    if(hi < right && (l0 == left || h[l0-1] < h[hi+1])){
       ++hi;
      height = min(height, h[hi]);
    }
    else{
      --l0;
      height = min(height, h[l0]);
    }
 
    //扩展后的长方形宽度
    ret = max(ret, height*(hi -l0 + 1));
  }
 
  return ret;
 
}