单调队列优化DP

题目传送门

简明题意：你初始时有$∞$ 元钱，并且每天持有的股票不超过 $Maxp$ 。有$T$ 天，你知道每一天的买入价格 $AP_i$ ，卖出价格 $Bp_i$，买入数量限制 $AS_i$，卖出数量限制 $BS_i$。并且两次交易之间必须间隔 $W$天。现在问你 $T$ 天结束后，最大收益是多少。

我们这么来想，股票买入我们可以看作是负收入

看过数据范围，我们考虑用 $DP$ 来解决这个问题

状态设计：

我们考虑用一个二维数组，显然我们首先需要记录天数，于是第一维就是天数

题目中还有一些限制，就是我们在满足收益最大的前提下，还要满足一些条件：

1，两次交易必须间隔$w$天

2，持有的股票数不得超过给定数

第一个限制条件我们很容易就可以解决，只需要在转移的时候控制一下天数就好了，我们可以直接用$DP$的第一维解决。

第二个限制呢？显然我们需要用一个新的维来记录这个问题，也就是我们需要用第二维来记录手里有多少股票。

于是设 $f[i][j]$ 为$i$天以后拥有$j$张股票所能获得的最大收益。

状态转移：

显然地存在三种大情况：

1，买股票

2，啥也不干

3，卖股票

首先对于买股票，我们又可以有两种，分别是凭空买和本来就有我再买。

啥也不干就显然了，我们就直接把前一天的搞过来就好了

麦股票显然就一种，我只能手里有的时候卖

于是我们有四种情况

case 1: 凭空买

因为直接买，我们就可以把这个初始状态直接赋值，其他的搞成 $-inf$.

$f[i][j]=-ap_i \times j \ ,\ ( 0\le j \le as_i)$

case 2:不买也不卖

直接把上一天的继承过来就可以了

$f[i][j]=max(f[i][j],f[i-1][j]),\ ( 0\le j \le maxp)$

case 3: 在之前的基础买股票

首先关于上面的问题 $1$，我们要满足之间间隔 $w$天，也就是上一次交易一定是在 $i-w-1$天的时候。

为什么我们一定在这一天进行交易？原因是我们在上一个 $case$ 中就解决了这个问题，我们已经把之前某一天以前的最优答案转移到了这一天，所以就不需要考虑以前的天数了，在这一天转移一定是比以前任何一天转移都要优的。

我们已知在第 $i$ 天拥有 $j$ 张股票，假设在第 $i-w-1$ 天有 $k$ 张股票。

$k$ 显然要比 $j$ 小，因为我们要买入，还有一个限制，我们一天最多买 $as_i$ 张，于是我们的 $k$ 的下线就是 $j-as_i$ 。

交易一共买入了 $j-k$ 张股票，要花 $(j-k) \times ap_i $ 元

那么方程就显而易见了：

$f[i][j]=max(f[i-w-1][k]-(j-k) \times ap_i) \ ,\ (j-as_i \le k \le j)$

case 4:卖股票

这个情况和上面那个很类似，但是略有不同。

这次因为要卖股票，所以 $k>j$,并且$k \le j+bs_i$.

本次交易卖出了 $k-j$ 张股票，赚钱 $(k-j) \times bp_i$ 元。

方程：

$f[i][j]=max(f[i-w-1][k]+(k-j) \times bp_i) \ ,\ (j \le k \le j+bs_i)$

优化：

对于 $case\ 3$ 和 $case\ 4$ ,如果我们直接计算，可以发现复杂度大概是 $O(n \times maxp ^2 )$ 的，妥妥的 $T$ 飞。

仔细观察式子：

$case\ 3:$
$f[i][j]=max(f[i-w-1][k]-(j-k) \times ap_i) \ ,\ (j-as_i \le k \le j)$

$case\ 4:$
$f[i][j]=max(f[i-w-1][k]+(k-j) \times bp_i) \ ,\ (j \le k \le j+bs_i)$

先来看$case\ 3$，我们把括号拆开，得：

$f[i][j]=max(f[i-w-1][k]-j \times ap_i +k \times ap_i) \ ,\ (j-as_i \le k \le j)$

发现其中有一项是不带 $k$ 的，我们把它提出来，得：

$f[i][j]=max(f[i-w-1][k]+k \times ap_i)-j
\times ap_i \ ,\ (j-as_i \le k \le j)$

在给定 $i,j$的时候，只有一个变量 $k$ ，也就是只有$k$ 的取值会影响答案。并且在 $j$ 的循环恰当的时候， $k$ 是具有平移关系的。

或者换句话说：这是符合单调性优化的条件的。

同样的，$case\ 4$ 我们同样可以得出类似的式子：

$f[i][j]=max(f[i-w-1][k]+k \times bp_i)-j \times bp_i \ ,\ (j \le k \le j+bs_i)$

于是我们使用单调队列，每次排除过期元素，然后补上新的选择，最后从对头取出最优解更新即可。

之后就是关于 $j$ 的循环顺序问题，我们要保证上一个状态已经有了。

对于 $case \ 3$ ，我们需要用到 $(j-k)$ 的状态,于是需要正序先算出小的。

对于 $case \ 4$ ，我们需要用到 $(k-j)$ 的状态,于是需要倒叙先算出大的。

于是 $case\ 3$ 正序， $case \ 4$ 倒序。

要说的就这么多了

CODE:

//#define LawrenceSivan

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

typedef long long ll;
typedef unsigned long long ull;
#define INF 0x3f3f3f3f
#define re register
const int maxn=2005;

inline int mymax(int x,int y){
	return x>y?x:y;
}

int T,maxp,w,ans;
int ap,bp,as,bs;
int f[maxn][maxn];
int q[maxn],l=1,r=0;

inline int read(){
    int x=0, f=1;char ch=getchar();
    while (!isdigit(ch)) {if(ch=='-')f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+(ch^48);ch=getchar();}
    return x*f;
}

int main() {
#ifdef LawrenceSivan
    freopen("aa.in", "r", stdin);
    freopen("aa.out", "w", stdout);
#endif
	memset(f,0xcf,sizeof(f));
	T=read();maxp=read();w=read();
	for(re int i=1;i<=T;i++){
		ap=read();bp=read();as=read();bs=read();
		for(re int j=0;j<=as;j++){//case 1
			f[i][j]=-1*j*ap;
		}
		
		for(re int j=0;j<=maxp;j++){// case 2
			f[i][j]=mymax(f[i][j],f[i-1][j]);
		}
		
		if(i<=w)continue;//如果i<=w，那么i-w-1就是负的了
		
		l=1;r=0;//case 3
		for(re int j=0;j<=maxp;j++){//low to high
			while(l<=r&&q[l]<j-as)l++;//排除过期元素
			while(l<=r&&f[i-w-1][q[r]]+q[r]*ap<=f[i-w-1][j]+j*ap)r--;//更新元素
			q[++r]=j;//插入最新元素
			if(l<=r)f[i][j]=mymax(f[i][j],f[i-w-1][q[l]]+q[l]*ap-j*ap);// 如果单调队列里有元素，即可转移
		}
		
		l=1;r=0;//case 4
		for(re int j=maxp;j>=0;j--){//high to low
			while(l<=r&&q[l]>j+bs)l++;//排除过期元素
			while(l<=r&&f[i-w-1][q[r]]+q[r]*bp<=f[i-w-1][j]+j*bp)r--;//更新元素
			q[++r]=j;//插入最新元素
			if(l<=r)f[i][j]=mymax(f[i][j],f[i-w-1][q[l]]+q[l]*bp-j*bp);
		}
	}
	
	for(re int i=0;i<=maxp;i++){//手上可以留下一点
		ans=mymax(ans,f[T][i]);
	}
	
	printf("%d\n",ans);


    return 0;
}

总结：

1，对于决策转移时，有明显单调性的情况，对于状态移动时，转移决策重复度较大。都可用单调队列优化。（滑动窗口）

2，对于单调性要主动发现，主动往那方面想

P2569 股票交易（单调队列优化DP）