POJ 2373 Dividing the Path 单调队列dp

两个队列 p和q

p存储当前所有已经访问过的节点

q对p中的节点进行筛选 选出可以对当前节点进行状态转移的节点，头节点就是最小值，维护这两个队列，时间复杂度就可以降下来

但是不清楚为什么模拟队列的时候永远是h = 1，t = 0

#include<iostream>
#include<cstring>
using namespace std;
const int maxn = 1e6+10;
int q[maxn],head=1,tail;
int p[maxn],h=1,t;
int f[maxn];
bool l[maxn];
int N,L,A,B;
int main()
{
	scanf("%d%d%d%d",&N,&L,&A,&B);
	for(int i = 1,s,e; i <= N; ++i)
	{
		scanf("%d%d",&s,&e);
		for(int j = s+1; j <= e-1; ++j) l[j] = 1;
	}
	memset(f,0x7f,sizeof(f));
	f[0] = 0; p[++t] = 0;
	for(int i = 2; i <= L; i+=2)
	{
		if(l[i]) continue;
		while(h<=t&&(i-p[h])/2>=A)
		{
			while(head<=tail&&f[q[tail]]>=f[p[h]]) tail--;
			q[++tail] = p[h++];
		}
		while(head<=tail && (i-q[head])/2>B) head++;
		if(head <= tail)
		{
			f[i] = f[q[head]]+1;
			p[++t] = i;
		}
	}
	if(f[L]!=0x7f7f7f7f) printf("%d\n",f[L]);
	else printf("-1\n");
	return 0; 
}