poj2373 Dividing the Path

Dividing the Path

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​​

题目大意：用若干条长度为[2a,2b]的线段覆盖区间，有一些区间要求只能被一整条线段覆盖，求最少用多少条线段可以覆盖完.

分析：考虑dp,设f[i]为覆盖到i所用的最少线段数.那么f[i] = min{f[j]} + 1 (i - 2*b ≤ j ≤ i - 2*a).这是一个很经典的用单调队列优化的dp.

每次用单调队列维护[i-2b,i-2a]这个区间的f值，挪动窗口更新fi的值.

          一些细节问题需要注意一下.枚举i,检查i与队首的距离是不是≤2b,接着把f[i-2a]放进队列里.最后取出队首更新fi的值.a,b,i不能弄混了.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int inf = 0x7ffffff;

int f[1000010],bg[1000010],ed[1000010],n,l,tag[1000010],pos[1000010],q[1000010],head,tail,a,b,num[1000010];

int main()
{
    scanf("%d%d",&n,&l);
    scanf("%d%d",&a,&b);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d%d",&bg[i],&ed[i]);
        for (int j = bg[i] + 1; j < ed[i]; j++)
            tag[j] = 1;
    }
    for (int i = 1; i <= l; i++)
        f[i] = inf;
    head = 1,tail = 0;
    f[0] = 0;
    for (int i = 2 * a; i <= l; i += 2) //因为线段长度是偶数，所以只用考虑偶数部分
    {
        while (head <= tail && i - num[head] > 2 * b)
            head++;
        while (head <= tail && q[tail] >= f[i - 2 * a])
            tail--;
        q[++tail] = f[i - 2 * a];
        num[tail] = i - 2 * a;
        if (!tag[i] && f[num[head]] != inf)
            f[i] = f[num[head]] + 1;
    }
    if (f[l] == inf)
        printf("-1\n");
    else
        printf("%d\n",f[l]);

    return 0;
}