POJ 2373 Dividing the Path(灌溉草场)

描述

在一片草场上:有一条长度为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 最少需要安装多少个喷水头。

输入

第1行：整数N、 L。
第2行：整数A、 B。
第3到N+2行：每行两个整数S、 E (0 <= S < E <= L) ，表示某头牛活动
范围的起点和终点在线段上的坐标(即到线段起点的距离)。

输出

最少需要安装的多少个喷水头；若没有符合要求的喷水头安装方案
，则输出-1。

样例输入

2 8
1 2
6 7
3 6

样例输出

3

分析

DP问题，状态转移方程为:

求f(X)=min(f(Y)) + 1, Y在[Y-2B, Y-2A]之间

其它更详细的实现看代码注释。

实现

代码实现来自北大课件，差别之处在于加了更详细的注释。

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int INFINITE = 1 << 31; //表示无解
const int MAXL = 1000010; //线段最大值，数值设大点是为了防止数据越界
const int MAXN = 1010; //奶牛数最大值
//状态：f(X)表示：所安装喷水头的喷洒范围恰好覆盖直线上的区间[0 X]时，最少需要多少个喷水头
int F[MAXL];
//cowThere[i]==1表示第i点有奶牛
int cowThere[MAXL];
int N, L, A, B;

struct Fx
{
    int x;
    int f;

    Fx(int xx = 0, int ff = 0) : x(xx), f(ff)
    {
    }

    bool operator <(const Fx& a) const
    {
        return f > a.f;
    }
};

//Fx.f值升序排列
priority_queue<Fx> qFx;

int main()
{
// freopen("in.txt", "r", stdin);
    cin >> N >> L >> A >> B;

    memset(cowThere, 0, sizeof(cowThere));
    for (int i = 0; i < N; i++) {
        int s, e;
        cin >> s >> e;
        //奶牛活动区间：(s, e)，用cowThere记录奶牛区间临界点
        ++cowThere[s + 1];
        --cowThere[e];
    }
    //输入数据为奶牛活动的半径，改为直径值，A、B都乘2后必为偶数，所以每次探索的右区间也为偶数
    A <<= 1;
    B <<= 1;

    //计算cowThere真正的值
    int inCows = 0; //当前点在多少头奶牛的活动范围之内
    for (int i = 0; i <= L; i++) {
        F[i] = INFINITE;
        inCows += cowThere[i];
        cowThere[i] = inCows > 0; //区间有进有出，类比()，用累加方式可能是否在区间内
    }
    //边界条件：f(X)=1： 2A<=X<=2B,且X位于任何奶牛的活动范围之外
    for (int i = A; i <= B; i += 2) {
        if (!cowThere[i]) {
            F[i] = 1;
            //下面求f(B+2)，不允许出现坐标大于X-2A的点
            if (i <= B + 2 - A) {
                qFx.push(Fx(i, 1));
            }
        }
    }
    //从f(B+2)一直计算到f(L), f(L)即为结果值
    for (int i = B + 2; i <= L; i += 2) {
        if (!cowThere[i]) {
            Fx fx;
            while (!qFx.empty()) {
                fx = qFx.top();
                //小于X-B的点抛弃，对f(X)而言，求f(X)=min(f(Y)) + 1, Y在[Y-B, Y-A]之间
                if (fx.x < i - B) {
                    qFx.pop();
                }
                else {
                    break;
                }
            }
            if (!qFx.empty()) {
                //状态转移方程：f(X)=min(f(Y)) + 1
                F[i] = fx.f + 1;
            }
        }

        //下一个点是X=i+2，加入下一个点所需f(Y)，Y在[i+2-B, i+2-A]之间
        if (F[i - A + 2] != INFINITE) {
            qFx.push(Fx(i - A + 2, F[i - A + 2]));
        }
    }
    if (F[L] == INFINITE) {
        cout << -1 << endl;
    }
    else {
        cout << F[L] << endl;
    }
    return 0;
}