题意：





思路：

f[i] = min(f[j]) + 1; 2 * ａ <= i - j <= 2 *ｂ；

i表示当前在第i个点。f[i]表示当前最少的线段个数

先是N^2的朴素DP（果断TLE）

//By SiriusRen

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

int n,l,A,B,tot=1,xx,yy,f[1000050];

struct Node{int x,y;}node[1050];

bool cmp(Node a,Node b){if(a.x!=b.x)return a.x<b.x;return a.y<b.y;}

int main()

{

    memset(f,0x3f,sizeof(f));

    f[0]=0;

    scanf("%d%d%d%d",&n,&l,&A,&B);

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

        scanf("%d%d",&node[i].x,&node[i].y);

    }

    sort(node+1,node+1+n,cmp);

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

        while(i>node[tot].x&&tot<n){i=node[tot].y;tot++;}

        if(i&1)continue;

        for(int j=2*A;j<=2*B;j+=2){

            f[i]=min(f[i],f[i-j]+1);

        }

    }

    printf("%d\n",f[l]);

}

下面我们开始想优化…

a和b都是常数，，他要找一个最大值。。

1.线段树优化 （卡时过）

2.单调队列优化

注意插入的时候要等到算f[i+2*a]的时候再把f[i]插到队列里。

（用STL的双端队列写得）

//By SiriusRen

#include <deque>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

int n,l,A,B,tot=1,xx,yy,f[1000050];

struct Node{int x,y;}node[1050],jy;

bool cmp(Node a,Node b){if(a.x!=b.x)return a.x<b.x;return a.y<b.y;}

deque<Node>q;

int main(){

    memset(f,0x3f,sizeof(f)),f[0]=0;

    scanf("%d%d%d%d",&n,&l,&A,&B);

    for(int i=1;i<=n;i++)scanf("%d%d",&node[i].x,&node[i].y);

    sort(node+1,node+1+n,cmp);

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

        for(int j=max(node[i].x+1,node[i-1].y);j<node[i].y;j++)f[j]=0x5fffffff;

    for(int i=A*2;i<=l;i+=2){

        while(!q.empty()&&q.front().x<i-2*B)q.pop_front();

        while(!q.empty()&&q.back().y>f[i-2*A])q.pop_back();

        if(f[i-2*A]<0x3ffffff)

            jy.x=i-2*A,jy.y=f[i-2*A],q.push_back(jy);

        if(f[i]>=0x4fffffff)continue;

        if(!q.empty())f[i]=q.front().y+1;

    }

    if(f[l]<0x3ffffff)printf("%d\n",f[l]);

    else puts("-1");

}