[POJ 2373] Dividing the Path【DP+单调队列优化】

  • 2018-01-23
  • 0
  • 0

Problem:

Time Limit: 1000MS Memory Limit: 65536K

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

Solution:

的单调队列 DP。。不过或许是我太了。。

思路很简单,就是在以 jmp[] 跳过不合法的喷水器边界的前提下,枚举当前边界为 i,用单调队列维护区间 [i - 2 * B, i - 2 * A] 的最小值,更新 dp[] 即可。

感觉是如此之水 ~~ 结果写好交上去就 WA 了。。定睛一看,原来是没有合并有重合部分的奶牛区间。。

于是大改特改。。然而交上去继续 WA 。。又不厌其烦地检查了一遍,结果发现合并的地方还是写错了 (见 Line 26) 。。

稍加修改又交了上去,结果还是 WA 。。找了半天,愣是没找出原因,网上找了个 AC 的程序对拍了很久,终于找到一个范围有几十万的数据,根本没法调试。。

最后终于发现了问题所在:所有的奇数位置均不能作为喷水器的左右边界! (见 Line 34)

。。

Code: O(L) [8532K, 94MS]

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
typedef pair<int, int> PII;

int N, L, A, B;
PII rg[1010];
int jmp[1000010], dp[1000010];
int q[1000010], fr, re;

int main(){
	scanf("%d%d%d%d", &N, &L, &A, &B), A <<= 1, B <<= 1;
	if(L & 1){
		puts("-1");
		return 0;
	}  // Actually the description has promised that L is even
	for(register int i = 0; i <= L; i++) jmp[i] = i + 1;
	for(register int i = 1; i <= N; i++) scanf("%d%d", &rg[i].first, &rg[i].second);
	sort(rg + 1, rg + N + 1);
	int curS = rg[1].first, curE = rg[1].second;
	for(register int i = 2; i <= N; i++)
		if(rg[i].first < curE) curE = max(curE, rg[i].second);  // An interval may contain another !!!!!!
		else jmp[curS] = curE, curS = rg[i].first, curE = rg[i].second;
	jmp[curS] = curE;
	// Merge the coincident intervals !!!
	memset(dp, 0x3f, sizeof(dp));
	#define SENTRY 1000009
	dp[0] = 0, fr = re = 1, jmp[q[0] = SENTRY] = 0;
	for(register int i = jmp[0]; i <= L; i = jmp[i]){
		if(i & 1) continue;  // The odd position cannot place any sprinkler !!!!!!!!!
		while(jmp[q[re - 1]] + A <= i){
			int cur = jmp[q[re - 1]];
			while(fr != re && dp[cur] <= dp[q[re - 1]]) re--;
			q[re++] = cur;
		}
		while(fr != re && q[fr] + B < i) fr++;
		if(fr != re && dp[q[fr]] != 0x3f3f3f3f)
			dp[i] = dp[q[fr]] + 1;
	}
	if(dp[L] != 0x3f3f3f3f) printf("%d\n", dp[L]);
	else puts("-1");
	return 0;
}

评论

还没有任何评论,你来说两句吧



常年不在线的QQ:
49750

不定期更新的GitHub:
https://github.com/Darkleafin


OPEN AT 2017.12.10

如遇到代码不能正常显示的情况,请刷新页面。
If the code cannot be displayed normally, please refresh the page.


发现一个优美的网站:
https://visualgo.net/en
















- Theme by Qzhai