单调队列优化

眼界极窄的ZZ之前甚至不会单调队列……（好丢人啊）
单调队列优化的常见情景：

• 转移可以转化成只需要确定一个维度，而且这个维度的取值范围在某个区间里

修剪草坪

这个题学长讲的好像是另外一个思路，但是码的时候不知不觉就偏到另一个思路里去了……改天也打打试试
需要注意的：

• 这题中如果有多个满足最大值，我们应该取最靠前的，所以在弹队的时候用的是>
• 这个题中单调队列维护的是\(dp_{j,0}-pre_j(i-k-1\leq j \leq i)\)，这里的\(j\)是入队时的下标
  精华：

	for(int i=1;i<=n;i++)
	{
		dp[i][0]=max(dp[i-1][1],dp[i-1][0]);
		while(fro<=bac&&Q[fro].id+k+1<=i)fro++;
		//ll t=Q[fro].id;
		dp[i][1]=Q[fro].v+pre[i];
		while(fro<=bac&&dp[i][0]-pre[i]>Q[bac].v)bac--;
		Q[++bac].v=dp[i][0]-pre[i];
		Q[bac].id=i;
	}

股票交易

这道题和上一道的特征很是不同……

• 如果多个满足最大值，这个题里不需要选最靠前的，所以弹队的时候用的是≥
• 这个题中单调队列维护的是（以买入举例，卖出同理）\(dp_{i-w-1,k}+k\cdot ap_i\)，而这里的\(i\)是每循环都会更新的，所以就不能偷懒在入队时算好了
• 手里没股票也是一种情况，所以算什么的时候都不要忘了考虑\(j=0\)的情况。
  （突然发现自己之前一直都在用一种诡异的结构体写法）
  精华：

for(int i=1;i<=t;i++)
	{
		for(int j=0;j<=as[i];j++)dp[i][j]=-j*ap[i];
		for(int j=0;j<=mp;j++)dp[i][j]=max(dp[i][j],dp[i-1][j]);//nothing
		if(i-w-1<0)continue;
		fro=1;bac=0;
		for(int j=0;j<=mp;j++)//buy
		{
			while(fro<=bac&&Q[fro]<j-as[i])fro++;
			while(fro<=bac&&dp[i-w-1][j]+ap[i]*j>=dp[i-w-1][Q[bac]]+ap[i]*Q[bac])bac--;
			Q[++bac]=j;
			if(fro<=bac)dp[i][j]=max(dp[i][j],dp[i-w-1][Q[fro]]+ap[i]*Q[fro]-j*ap[i]);
		}
		fro=1;bac=0;
		for(int j=mp;j>=0;j--)
		{
			while(fro<=bac&&Q[fro]>j+bs[i])fro++;
			while(fro<=bac&&dp[i-w-1][j]+bp[i]*j>=dp[i-w-1][Q[bac]]+bp[i]*Q[bac])bac--;
			Q[++bac]=j;
			if(fro<=bac)dp[i][j]=max(dp[i][j],dp[i-w-1][Q[fro]]+bp[i]*Q[fro]-j*bp[i]);
		}
	}

【刷题笔记】DP优化-单调队列优化

原文：https://www.cnblogs.com/zzzuozhe-gjy/p/12800750.html