Dividing the Path(POJ 灌溉草场) 动态规划 优先队列

本文主要是介绍Dividing the Path(POJ 灌溉草场) 动态规划 优先队列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Dividing the Path点击转到

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 5588		Accepted: 1968

Description

Farmer John's cows have discovered that the clover growing along the ridge of the hill in his field is particularly good. To keep the clover watered, Farmer John is installing water sprinklers along the ridge of the hill. 

To make installation easier, each sprinkler head must be installed along the ridge of the hill (which we can think of as a one-dimensional number line of length L (1 <= L <= 1,000,000); L is even). 

Each sprinkler waters the ground along the ridge for some distance in both directions. Each spray radius is an integer in the range A..B (1 <= A <= B <= 1000). Farmer John needs to water the entire ridge in a manner that covers each location on the ridge by exactly one sprinkler head. Furthermore, FJ will not water past the end of the ridge in either direction. 

Each of Farmer John's N (1 <= N <= 1000) cows has a range of clover that she particularly likes (these ranges might overlap). The ranges are defined by a closed interval (S,E). Each of the cow's preferred ranges must be watered by a single sprinkler, which might or might not spray beyond the given range. 

Find the minimum number of sprinklers required to water the entire ridge without overlap. 

Input

* Line 1: Two space-separated integers: N and L 

* Line 2: Two space-separated integers: A and 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.

Output

* Line 1: The minimum number of sprinklers required. If it is not possible to design a sprinkler head configuration for Farmer John, output -1.

Sample Input

2 8
1 2
6 7
3 6

Sample Output

3

Hint

INPUT DETAILS: 

Two cows along a ridge of length 8. Sprinkler heads are available in integer spray radii in the range 1..2 (i.e., 1 or 2). One cow likes the range 3-6, and the other likes the range 6-7. 

OUTPUT DETAILS: 

Three sprinklers are required: one at 1 with spray distance 1, and one at 4 with spray distance 2, and one at 7 with spray distance 1. The second sprinkler waters all the clover of the range like by the second cow (3-6). The last sprinkler waters all the clover of the range liked by the first cow (6-7). Here's a diagram: 

                 |-----c2----|-c1|       cows' preferred ranges|---1---|-------2-------|---3---|   sprinklers+---+---+---+---+---+---+---+---+0   1   2   3   4   5   6   7   8

The sprinklers are not considered to be overlapping at 2 and 6.

Source

USACO 2004 December Gold

1.题目含义：

      在一片草场上:有一条长度为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.解题思路：

 2.1  X满足：

        2.1.1X为偶数（因为X为奇数，将不能灌溉整个L区域）
     2.1.2X所在位置不会出现奶牛，即X不属于任何一个(S,E)
     2.1.3 X大于等于2A
     2.1.4 当X大于2B时，存在Y属于 [X-2B X-2A]   且Y满足上述三个条件，使得f(X)=f(Y)+1

  2.2  递推计算f(X)
f(X) = ∝ ： X 是奇数
f(X) = ∝ ： X < 2A
f(X) = ∝ ：X处可能有奶牛出没
f(X)=1： 2AX2B 、且X位于任何奶牛的活动范围之外
f(X)=1+min{f(Y): Y[X-2B X-2A]、Y位于任何奶牛的活动范围之外}： X>2B

3.本题可以学习，牛活动区域的存储问题。（区间标记）

#include<iostream>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#include<cmath>
#include<cstdlib>
using namespace std;
#define maxl 1000010
#define maxn 1010
#define inf 0x3f3f3f3f
int f[maxl];
int cow[maxl];
int n,l,a,b;
struct ans
{int x,f;//f是喷水头的个数 bool operator<(const ans &a)const{return f>a.f;//从小到大排序 }ans(int xx=0,int yy=0):x(xx),f(yy){}
};
priority_queue<ans> q;
int main()
{cin>>n>>l;cin>>a>>b;while(!q.empty()){q.pop();}a=a*2;//变为直径 b=b*2;int s,e;memset(cow,0,sizeof(cow));for(int i=0;i<n;i++){cin>>s>>e;++cow[s+1];//从s+1处起，进入一个奶牛活动的区域 --cow[e];//一个奶牛活动区域，结束的边界 }int nowcows=0;//表示当前节点，位于多少头奶牛的活动范围之内 for(int i=0;i<=l;i++)//记录每个节点，是否有奶牛 {f[i]=inf;nowcows=nowcows+cow[i];cow[i]=nowcows;}//for(int i=0;i<=l;i++) //cout<<cow[i]<<"*****"<<i<<endl;for(int i=a;i<=b;i+=2)//队列初始化 {if(!cow[i]) {f[i]=1;if(i<=b+2-a){q.push(ans(i,1));}}}for(int i=b+2;i<=l;i+=2)//y位于[X-2*B,X-2*A]范围内的时候 {if(!cow[i])//位于奶牛的活动范围之外，且在[X-2*B,X-2*A]之间 {ans x;while(!q.empty()){x=q.top();if(x.x<i-b) {q.pop();}else break;}if(!q.empty())f[i]=x.f+1;}if(f[i-a+2]!=inf){q.push(ans(i-a+2,f[i-a+2]));}}if(f[l]==inf)  cout<<-1<<endl;else cout<<f[l]<<endl;return 0;
}

 

这篇关于Dividing the Path(POJ 灌溉草场) 动态规划 优先队列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---