博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
POJ 2373 Dividing the Path(DP + 单调队列)
阅读量:4600 次
发布时间:2019-06-09

本文共 3403 字,大约阅读时间需要 11 分钟。

描述

农夫约翰的牛发现,在他的田里沿着山脊生长的三叶草是特别好的。为了给三叶草浇水,农夫约翰在山脊上安装了喷水器。
为了使安装更容易,每个喷头必须安装在山脊上(我们可以认为这是一条长度为L(1<=L<=1,000,000)的一维数列;L是偶数)。
每个洒水器沿山脊向两个方向地面排水一段距离。每个喷雾半径是A.B范围内的整数(1<=A<=B<=1000)。农夫约翰需要给整个山脊浇水,用一个喷头覆盖整个山脊上的每一个位置。此外,FJ不会在任何一个方向超过山脊的末端。
每头农场主约翰的N(1<=N<=1000)奶牛都有她特别喜欢的一系列三叶草(这些范围可能重叠)。范围由闭区间(S,E)定义。母牛的每一个选择范围都必须用一个喷头浇水,这种喷头可能会也可能不会在给定的范围内喷水。
找出最小数量的喷头需要浇水整个山脊没有重叠。

输入

*第1行:两个空格分隔的整数:n和L
*第2行:两个空格分隔的整数:A和B
* Lines 3..N+2: Each line contains two integers, S and E (0 <= S < E <= L) specifying the start end location respectively of a range preferred by some cow. Locations are given as distance from the start of the ridge and so are in the range 0..L.

输出量

*第1行:所需的最少喷头数目。如果不可能为农民约翰设计喷头配置,输出-1。

样本输入

2 81 26 73 6

样本输出

3

暗示

输入详情:
两头母牛沿着一条8长的山脊。喷头在1.2(即1或2)范围内有整数的喷雾半径。一只母牛喜欢3-6的范围,另一只喜欢6-7的范围。
产出详情:
需要三个喷头:一个喷淋距离为1,一个喷淋距离为4,喷雾距离为2,另一个喷淋距离为7,喷雾距离为1。第二个洒水器像第二头牛(3-6)一样,将整个范围内的三叶草全部浇水。最后的洒水所有的范围内的三叶草喜欢的第一头牛(6-7)。下面是一个图表:
|-----c2----|-c1|       cows' preferred ranges      |---1---|-------2-------|---3---|   sprinklers      +---+---+---+---+---+---+---+---+      0   1   2   3   4   5   6   7   8
喷头在2和6处不被认为是重叠的。
 
解题思路:

从线段的起点向终点安装喷水头,令f(X)表示:所安装喷水头的喷洒范围 恰好覆盖直线上的区间[0 X]时,最少需要多少个喷水头

显然,X应满足下列条件:

  X为偶数

  X所在位置不会出现奶牛,即X不属于任何一个(S,E)

  X>=2A

  当X<=2B时,存在Y属于[X-2B X-2A]且Y满足上述三个条件,使得 f(X)=f(Y)+1 

对每个X求f(X),都要遍历区间 [X-2B, X -2A]去寻找其中最小的 f(Y),则时间复杂度为:L * B = 1000000 * 1000,太慢,快速找到[X-2B X-2A]中使得f(Y)最小的元素是问题求解速度的关键 。

!!!

可以使用优先队列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)作准备

代码:

#include
#include
using namespace std;const int INF = 0x3f3f3f;const int MAXL = 1000010;int cowThere[MAXL];//cowThere[i]为1表示点i有奶int dp[MAXL];// dp[L]就是答案 struct Fx { int x; int f; bool operator<(const Fx & a) const { return f > a.f; } Fx(int xx=0,int ff=0):x(xx),f(ff) { } };// 在优先队列里,f值越小的越优先priority_queue
qFx;int main() { int N, L, A, B; cin >> N >> L; cin>> A >> B;//A,B的定义变为覆盖的直径 A <<= 1; B <<= 1; for(int i = 0; i < N; i++) { int s, e; cin >> s >> e; cowThere[s+1]++;//从s+1进入一个奶牛区 cowThere[e]--;//从e起退出一个奶牛区 } int inCows = 0; //表示当前点位于多少头奶牛的活动范围之内 for(int i = 0; i <= L; i++) {
//算出每个点是否有奶牛 dp[i] = INF; inCows += cowThere[i]; cowThere[i] = inCows > 0; } for(int i = A; i <= B; i += 2) {
//初始化队列 if(!cowThere[i]) { dp[i] = 1; if(i <= B + 2 - A) {
//在求dp[i]的时候,要确保队列里的点x,x <= i - A qFx.push(Fx(i, 1)); } } } for(int i = B + 2; i <= L; i += 2) { if(!cowThere[i]) { Fx fx; while(!qFx.empty()) { fx = qFx.top(); if(fx.x < i - B) qFx.pop(); else break; } if(!qFx.empty()) { dp[i] = fx.f + 1; } } //队列中增加一个可达下个点的点,为下一个dp(i+2)做准备 if(dp[i + 2 - A] != INF) qFx.push(Fx(i + 2 - A, dp[i + 2 - A])); } if(dp[L] == INF) cout << -1 << endl; else cout << dp[L] << endl; return 0;}

转载于:https://www.cnblogs.com/kindleheart/p/9505090.html

你可能感兴趣的文章
构建Docker Compose服务堆栈
查看>>
浮点数内存如何存储的
查看>>
JsonCpp 的使用
查看>>
问题账户需求分析
查看>>
hp 服务器通过串口重定向功能的使用
查看>>
此博客不再发表对自己私事的看法
查看>>
导致Asp.Net站点重启的10个原因
查看>>
【PMP】Head First PMP 学习笔记 第一章 引言
查看>>
抓住云机遇编排工作 搞定复杂IT工作流
查看>>
MYSQL的longtext字段能放多少数据?
查看>>
MTK 平台上如何给 camera 添加一种 preview size
查看>>
云计算最大难处
查看>>
mysql定时备份自动上传
查看>>
17岁时少年决定把海洋洗干净,现在21岁的他做到了
查看>>
《写给大忙人看的java se 8》笔记
查看>>
倒计时:计算时间差
查看>>
Linux/windows P2V VMWare ESXi
查看>>
Windows XP倒计时到底意味着什么?
查看>>
运维工程师在干什么学些什么?【致菜鸟】
查看>>
Linux中iptables详解
查看>>