动态规划 例题：灌溉草场
在一片草场上:有一条长度为L (1 <= L <= 1,000,000，L为偶数)的线 段。 John的N (1 <= N <= 1000) 头奶牛都沿着草场上这条线段吃草，每头 牛的活动范围是一个开区间(S,E)，S，E都是整数。不同奶牛的活动范围可以 有重叠。 John要在这条线段上安装喷水头灌溉草场。每个喷水头的喷洒半径可以随 意调节，调节范围是 [A B ](1 <= A <= B <= 1000)，A,B都是整数。要求 线段上的每个整点恰好位于一个喷水头的喷洒范围内 每头奶牛的活动范围要位于一个喷水头的喷洒范围内 任何喷水头的喷洒范围不可越过线段的两端(左端是0,右端是L ) 请问， John 最少需要安装多少个喷水头。
在位置2和6，喷水头的喷洒范围不算重叠
问题分析：
解题思路：
解题思路：
可以使用优先队列priority_queue! (multiset也可以，比 priority_queue慢一点）!
求F(X)时，若坐标属于[X-2B, X-2A]的二元组(i,F(i))都保存在 一个priority_queue中,并根据F(i)值排序，则队头的元素就能 确保是F(i)值最小的。
在求 X点的F(x)时，必须确保队列中包含所有属于 [X-2B,X-2A]的点。 而且，不允许出现坐标大于X-2A的点，因为这样的点对求F(X)无用，如 果这样的点出现在队头，因其对求后续点的F值有用，故不能抛弃之， 于是算法就无法继续了。
队列中可以出现坐标小于 X-2B 的点。这样的点若出现在队头，则直接 将其抛弃。
求出X点的F值后，将(X-2A+2, F(X-2A+2))放入队列，为求F(X+2)作准 备
队列里只要存坐标为偶数的点即可
手工实现优先队列的方法
如果一个队列满足以下条件：
1) 开始为空
2) 每在队尾加入一个元素a之前，都从现有队尾往前删除元素， 一直删到碰到小于 a的元素为止，然后再加入a 那么队列就是递增的，当然队头的元素，一定是队列中最小 的
特别声明：以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布，本平台仅提供信息存储服务。
Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.
