poj 2373 单调队列优化dp
单调队列优化dp
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int maxl=1e6+9,maxn=1e3+9;int dp[maxl],que[maxl],top,front;int n,m,l,r;bool use[maxl];struct D{ int l,r; bool operator <(const D & xx) const { return l<xx.l; }}data[maxn];void init(){ memset(use,0,sizeof(use)); memset(dp,50,sizeof(dp)); dp[0]=top=0; front=1;}inline void push(int que[],int &front,int &top,int t){ while(top>=front&&dp[t-l]<dp[que[top]]) top--; que[++top]=t-l;}inline void pop(int que[],int &front,int &top,int t){ while(front<=top&&t-que[front]>r) front++;}int main(){// freopen("in.txt","r",stdin); while(scanf("%d %d",&n,&m)!=EOF) { init(); scanf("%d %d",&l,&r); for(int i=1;i<=n;i++) scanf("%d %d",&data[i].l,&data[i].r); sort(data+1,data+1+n); for(int i=1,to=0;i<=n;i++) { int tmp=max(to,data[i].l+1); for(int j=tmp;j<data[i].r;j++) use[j]=1; to=max(to,data[i].r-1); } l<<=1,r<<=1; for(int i=l;i<=m;i+=2) { if(!use[i-l]) push(que,front,top,i); pop(que,front,top,i); if(front<=top&&!use[i]) dp[i]=dp[que[front]]+1; } if(dp[m]<1e7) cout<<dp[m]<<endl; else cout<<-1<<endl; } return 0;}