昵称192
2021-11-26 11:44
采纳率: 0%
浏览 58

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

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

  • 写回答
  • 好问题 提建议
  • 关注问题
  • 收藏
  • 邀请回答

2条回答 默认 最新

  • 许彦强code 2021-11-26 11:49
    
    //保存各个木板高度的数组
    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;
     
    }
    
    评论
    解决 无用
    打赏 举报
  • 社区助手 2021-11-26 12:34

    亲爱的提问者您好,我们很乐意您能在CSDN解决编程过程中遇到的问题,
    但是问答频道谢绝一切直接提问作业、索要代码的行为,在此对您发出正式警告。
    后续如果继续不加思考,直接提出作业问题,我们会限制您在问答频道的提问权益。
    CSDN也鼓励用户通过举报功能来对这些行为进行监督反馈,共建问答频道良好的风气。

    评论
    解决 无用
    打赏 举报

相关推荐 更多相似问题