POJ2373 Dividing the Path - dblank

POJ2373 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

题意:在一片草场上:有一条长度为L (1 <= L <= 1,000,000,L为偶数)的线段。 John的N (1 <= N <= 1000) 头奶牛都沿着草场上这条线段吃草,每头牛的活动范围是一个开区间(S,E),S,E都是整数。不同奶牛的活动范围可以有重叠。John要在这条线段上安装喷水头灌溉草场。每个喷水头的喷洒半径可以随意调节,调节范围是 A B ,A,B都是整数。要求线段上的每个整点恰好位于一个喷水头的喷洒范围内
每头奶牛的活动范围要位于一个喷水头的喷洒范围内任何喷水头的喷洒范围不可越过线段的两端(左端是0,右端是L )请问, John 最少需要安装多少个喷水头。

思路:dp[i]表示到长度为i的最小需要个数,因为要覆盖所有的点,所以对于dp[i]可以是从[i-2b, i-2a]的最小状态转移过来,然后长度必须是偶数,所以奇数的i可以直接跳过,我们可以把所有的点加入到一个优先队列里面,从优先队列里面取一个满足覆盖要求的最小个数,转态转移。注意到,如果一个点大于i-2ad的话是不能加入到队列里面的,不足i-2b的可以直接出队。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
using namespace std;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f, N = 1000000 + 10, Mod = 1000000000;
typedef long long ll;
int dp[N], vis[N];
struct node
{
    int f, s;
    bool operator < (const node & P) const
    {
        return f > P.f;
    }
    node() {};
    node(int _f, int _s): f(_f), s(_s) {}
};
int main()
{
    int n, l, a, b, s, e;
    while(cin>>n>>l)
    {
        cin>>a>>b;
        a*=2;
        b*=2;
        memset(vis, 0, sizeof(vis));
        memset(dp, 0x3f, sizeof(dp));
        for(int i = 1; i<=n; i++)
        {
            scanf("%d%d", &s, &e);
            for(int j = s+1; j<=e-1; j++)
                vis[j] = 1;           //因为要覆盖所有的牛活动的区间,所以这些要被标记,直接跳过
        }
        priority_queue<node> q;
        for(int i = a; i<=b; i+=2)
        {
            if(!vis[i])
                dp[i] = 1;
            if(i+a<=b+2 && !vis[i])
                q.push(node(1, i));//将首先的一个加入到队列
        }
        node x;
        for(int i = b+2; i<=l; i+=2)
        {
            if(!vis[i])
            {
                while(!q.empty()) // 找到一个满足条件的队首元素
                {
                    x = q.top();
                    if(x.s + b < i)
                        q.pop();
                    else break;
                }
                if(!q.empty())
                {
                    dp[i] = x.f + 1;
                }
            }
            if(dp[i-a+2]!=inf)      //将后面一个加入到队列
                q.push(node(dp[i-a+2], i-a+2));
        }
        if(dp[l] == inf)
            printf("-1n");
        else printf("%dn", dp[l]);
    }
    return 0;
}

 

相关文章

发表新评论