Description：

初始有无穷的钱，每天持有股票不超过 $MAXP$ ，知道 $T$ 天内每天的买入价格 $AP[i]$ ，卖出价格 $BP[i]$ ，买入数量限制 $AS[i]$ ，卖出数量限制 $BS[i]$ ，两次交易至少间隔 $W$ 天，问 $T$ 天后的最大收益。

$1\le T,MAXP \le 2000$

Solution：

猜想 $DP$ 状态为 $f[i][j]$ 表示 $i$ 天持有 $j$ 股的最大收益，转移有 $3$ 种：

$1$ 、什么都不做： $f[i][j]=f[i-1][j]$

$2$ 、买入： $f[i][j]=f[i-w-1][k]+(k - j)\times AP[i](j-AS[i]\le k < j)$

$3$ 、卖出： $f[i][j]=f[i-w-1][k]+(k-j)\times BP[i](j<k\le j+BS[i])$

看到后面的区间取最大值可以单调队列维护滑动窗口。

关于间隔限制只要每次从 $i-w-1$ 转移过来即可。

然而还有一种方案，就是在之前不买任何股票的情况下直接在这个点买股票，这样买不受 $W$ 的限制，所以不会在买入中被计算，必须特殊转移。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,maxp,w;

#define MAXN 2010

int ap[MAXN],bp[MAXN],as[MAXN],bs[MAXN];

int f[MAXN][MAXN];

int q[MAXN],head = 1,tail = 0;

int main()

{

	scanf("%d%d%d",&n,&maxp,&w);

	for(int i = 1;i <= n;++i)scanf("%d%d%d%d",&ap[i],&bp[i],&as[i],&bs[i]);

	memset(f,0xc0,sizeof(f));

	f[0][0] = 0;

	for(int i = 1;i <= n;++i)

	{

		for(int j = 0;j <= maxp;++j)f[i][j] = f[i - 1][j];

		for(int j = 0;j <= as[i];++j)f[i][j] = max(f[i][j],-ap[i] * j);

		if(i > w)

		{

			memset(q,0,sizeof(q));head = 1;tail = 0;

			q[++tail] = 0;

			for(int j = 1;j <= maxp;++j)

			{

				while(head <= tail && q[head] < j - as[i])++head;

				f[i][j] = max(f[i][j],f[i - w - 1][q[head]] + (q[head] - j) * ap[i]);

				while(head <= tail && f[i - w - 1][j] + j * ap[i] >= f[i - w - 1][q[tail]] + q[tail] * ap[i])--tail;

				q[++tail] = j;

			}

			memset(q,0,sizeof(q));head = 1;tail = 0;

			q[++tail] = maxp;

			for(int j = maxp - 1;j >= 0;--j)

			{

				while(head <= tail && q[head] > j + bs[i])++head;

				f[i][j] = max(f[i][j],f[i - w - 1][q[head]] + (q[head] - j) * bp[i]);

				while(head <= tail && f[i - w - 1][j] + j * bp[i] >= f[i - w - 1][q[tail]] + q[tail] * bp[i])--tail;

				q[++tail] = j;

			}

		}

	}

	cout << f[n][0] << endl;

	return 0;

}