Dividing the Path POJ - 2373 dp

题意：你有无数个长度可变的区间d  满足 2a<=d<=2b且为偶数. 现在要你用这些区间填满一条长为L（L<1e6且保证是偶数）的长线段。

　　满足以下要求：

　　1.可变区间之间不能有交集，且不能超过长线段的左右边界

　　2.长线段上有若干短线段，给出他们的起始点与终点。你要保证对于任意一条短线段，你的某个区间可以完全包含它。

　　求最少需要多少个可变区间。

题解：用dp[x]表示填到x距离所需要最少的可变区间数。

　　　　分析发现x必定满足：

　　　　1.偶数

　　　　2.x不能在某条短线段上//若不然，则x在某条短线段上，则说明这条短线段未被包含，可以令dp[x]=INF；

　　　　3.x>=2A;//换言之，对于x<2A的x，是无法满足要求的，可以令dp[x]=INF

　　　　4.当x>2B时，存在 x-2B<=y<=x-2A  且满足上面三条的y，使得f[x]=f[y]+1;

　　

由此对应的递推方程：

技巧：对于取min操作，我们用priorityqueue来优化（nlogn），用-1来从小到大排queue。对于奶牛出现的位置用线性算法处理（n）。对于 x-2B<=y<=x-2A 的处理，直接就不把他们push进queue里了，然后及时把不符合的pop掉。

坑：以后一些明显没错的东西就别xjb乱改了//其实是少写了个=号，wa了一页。

代码如下：

#define _CRT_SECURE_NO_WARNINGS

#include<iostream>

#include<cstring>

#include<queue>

#include<string.h>

using namespace std;

const int INF =1e9;

const int maxn = 1e3 + ;

const int maxl = 1e6 + ;

int dp[maxl];//长度为i时所需最少的喷头

int cow[maxl];//cow[i]==1代表有牛；用一个线性算法记录

int n, l, a, b;

priority_queue<pair<int,int>> qfx;

int main() {

    cin >> n >> l;

    cin >> a >> b;

    a <<= , b <<= ;//覆盖直径

    memset(cow, , sizeof(cow));

    for (int i = ; i < n; i++) {

        int s, e;

        cin >> s >> e;

        ++cow[s + ];

        --cow[e];

    }

    int incows = ;

    for (int i = ; i <= l; i++) {

        dp[i] = INF;

        incows += cow[i];

        cow[i] = (incows > );

    }

    for (int i = a; i <= b; i+=) if (!cow[i]) {

            dp[i] = ;

            if (i <= b +  - a)qfx.push(make_pair(-,i));

    }

    for (int i = b + ; i <=l; i+=) {

        if (!cow[i]) {

            pair<int,int> now;

            while (!qfx.empty()) {

                now = qfx.top();

                if (now.second < i - b) qfx.pop();

                else break;

            }

            if (!qfx.empty()) dp[i] = -now.first + ;

        }

        if (dp[i -a+] != INF)qfx.push(make_pair(-dp[i - a + ],i - a +  ));

    }

    if (dp[l] == INF) cout << -<<endl;

    else cout << dp[l]<<endl;

    return ;

 }