对本题单调队列做法熟悉dalao的帮忙解答一下。

看了题解，基本都是用两个队列，第一个队列存“下标”，第二个队列存对应的最优值。但其实第二个队列中的值也是通过第一个队列中存在“下标”计算得到的，两个队列元素是一一对应的。那只用第一个队列应该是可以的，但是我用两个队列就可以AC，只用一个就有问题。自己调了很久没理解，dalao帮忙看看，谢谢。

首先是用两个队列的AC代码

#include <bits/stdc++.h>
using namespace std;

int n,W;
int v,w,m;
int f[40005];
int Que[40005],Que2[40005];

int main(){
	scanf("%d %d",&n,&W);
	for(int i=1;i<=n;i++){	//枚举每个物品
		scanf("%d %d %d",&v,&w,&m);
		
		/**	令容量 j=r+kw 
			f[j]= f[r+kw] 
				= max{ f[r+qw]+(k-q)*v | q=0,1...k }
				= max{ f[r+qw]-q*v     | q=0,1...k } + k*v	
		*/
		for(int r=0;r<w;r++){	//枚举余数r		
			int head=0,tail=-1,k=(W-r)/w;
			for(int q=0;q<=k;q++){	//枚举倍数q
				while(head<=tail && f[r+q*w]-q*v>=Que2[tail]) tail--;
				Que[++tail]=q;
				Que2[tail]=f[r+q*w]-q*v;
		
				if(head<=tail && q-Que[head]>m) head++;
			
				f[r+q*w]=Que2[head]+q*v;
			}
		}
	}
	printf("%d",f[W]);
	return 0;
}

上面代码中，Que是“下标”队列，Que2是对应的最优值队列，元素一一对应，Que2[i]=f[r+Que[i]*w]-Que[i]*v ,但是按这种方式改成只用一个队列的方式就有问题了（只列出更改部分）

		for(int r=0;r<w;r++){	//枚举余数r		
			int head=0,tail=-1,k=(W-r)/w;
			for(int q=0;q<=k;q++){	//枚举倍数q
				while(head<=tail && f[r+q*w]-q*v>=f[r+Que[tail]*w]-Que[tail]*v) tail--;
				Que[++tail]=q;
	
				if(head<=tail && q-Que[head]>m) head++;
			
				f[r+q*w]=f[r+Que[head]*w]-Que[head]*v+q*v;
			}
		}