POJ2373动态规划

单调队列优化的dp。首先我们先进行预处理，将可以合并的区间合并到一起，这个可以在O(nlogn)的时间内完成。方法是按照x排序，然后找相邻的两个区间(a,b)和(c,d)是否满足a<d并且b>c，注意这里必须严格大于才行，因为这里的区间都是开区间，如果存在b==c这样的情况，那么b这个点就可以分割。
然后进行动态规划转移，令dp[i]为前i个区间可以划分的最小区间数目，那么就有：
dp[i]=min{dp[i-2*k]}+1,  A<=k<=B，如果不存在这样的k值，或者i是在某个区间内，那么dp[i]就为oo，注意初始化dp[0]=1, dp[1]=oo。
运用类似多重背包的方法将i划分成2的一个剩余类，也就是说我们可以对上式进行变形，变成如下的形式：
dp[mod+2*j]=min{dp[mod+2*k]}+1, A<=j-k<=B，这里dp[mod+2*j]是个仅关于j的函数，可以用单调队列维护一定区间的最值，最后问题得到解决。
注意这题的一些细节，首先当L为奇数的时候dp[L]与dp[1]属于同一个剩余类，那么dp[L]就为oo，所以直接可以输出-1。其次，对于判断i是否在区间内，可以用一个指针p动态向后移动的方式来判断，如果第p个区间的右边界小等于i，那么p就右移，知道p等于n或者右边界大于i为止，这时候判断第p个区间的左边界是否比i小，如果左边界小于i，那么dp[i]就是oo。最后，如果dp[L]等于oo记得输出-1。
这里还有一个很好的技巧，在队列中加一个哨兵oo，它的id也为oo，这样可以处理如果i<A的情况，当然也可以直接预处理出对所有的i<A都有dp[i]=oo，注意这里枚举和0的同剩余类的元素要从2开始循环！

我的代码：

#include <cstdio> #include <cstring> #include <cstdlib> #include <vector> #include <algorithm> using namespace std; const int MAX=1001000; const int oo=0x3f3f3f3f; int dp[MAX]; struct Seg{ int x,y; Seg(int x=0,int y=0):x(x),y(y){} bool operator<(const Seg& seg) const{ return x<seg.x; } }seg[1100]; int q[MAX],id[MAX],f,b; int merge(int n){ int top=0; sort(seg,seg+n); int l=seg[0].x,r=seg[0].y; for(int i=1;i<n;i++){ if(seg[i].x<r){ r=max(r,seg[i].y); }else{ seg[top++]=Seg(l,r); l=seg[i].x; r=seg[i].y; } } seg[top++]=Seg(l,r); return top; } int main(){ int n,L,l,r,p; scanf("%d%d",&n,&L); if(L&1){ printf("%d/n",-1); return 0; } scanf("%d%d",&l,&r); for(int i=0;i<n;i++){ scanf("%d%d",&seg[i].x,&seg[i].y); } n=merge(n); l<<=1; r<<=1; dp[0]=0; f=b=0; p=0; dp[0]=0; for(int i=2;i<l;i+=2)dp[i]=oo; //start with 2. for(int i=l;i<=L;i+=2){ while(f!=b&&i-id[f]>r)f++; while(f!=b&&q[b-1]>=dp[i-l])b--; id[b]=i-l; q[b++]=dp[i-l]; while(p<n&&seg[p].y<=i)p++; if(p<n&&seg[p].x<i||q[f]==oo)dp[i]=oo; //if q[f] is oo, not to set dp[i] = q[f]+1. else dp[i]=q[f]+1; } //for(int i=0;i<=L;i+=2)printf("%d ",dp[i]==oo?-1:dp[i]);puts(""); printf("%d/n",dp[L]==oo?-1:dp[L]); return 0; }