题目地址

P3572 [POI2014]PTA-Little Bird

都是手写的双端队列，但是这两段dp操作有什么区别？第一段答案都少了个1，第二段正常的

第一段代码：

inline void dp(int t)
{
	head=tail=0;
	deq[++tail]=1;
	for (rint i=2;i<=n;++i)
	{
		f[t][i]=f[t][deq[head+1]]+(d[head+1]<=d[i]);
		while(tail>head)
		{
			if (f[t][deq[tail]]<f[t][i]||(f[t][deq[tail]]==f[t][i]&&d[deq[tail]]>d[i]))
			break;
			--tail;
		}
		deq[++tail]=i;
		while(tail>head)
		{
			if ((i+1-deq[head+1])<=k[t])
			break;
			++head;
		}
	}
	printf("%d\n",f[t][n]);
}

第二段代码：

inline void dp(int t)
{
	head=tail=0;
	deq[++tail]=1;
	int tmp,cnt;
	for (rint i=2;i<=n;++i)
	{
		tmp=deq[head+1];
		f[t][i]=f[t][tmp]+(d[tmp]<=d[i]);
		cnt=deq[tail];
		while(tail-head)
		{
			if (f[t][cnt]<f[t][i]||(f[t][cnt]==f[t][i]&&d[cnt]>d[i]))
			break;
			cnt=deq[--tail];
		}
		deq[++tail]=i;
		while(tail-head)
		{
			if ((i+1-tmp)<=k[t])
			break;
			tmp=deq[++head+1];
		}
	}
	printf("%d\n",f[t][n]);
}