luogu P2569 [SCOI2010]股票交易 單調優化dp

參考：https://www.luogu.com.cn/blog/Sooke/solution-p2569

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int N=2001;
int n,m,w;
int ap,bp,as,bs;
int ans;
int f[N][N] ;// f[i][j] 表示第 i 天後擁有 j 張股票賺的最多錢數
int hh,tt,q[2001];
int main()
{
	cin>>n>>m>>w;
	memset(f,128,sizeof f); // 128 實際上給 f 數組賦的是 -inf，可以試試看
	for(int i=1;i<=n;i++)
	{
		//買入價格，賣出價格，最多買，最多賣
		cin>>ap>>bp>>as>>bs;
		for(int j=0;j<=as;j++)
			f[i][j]=-1*j*ap; //憑空買
		for(int j=0;j<=m;j++)
			f[i][j]=max(f[i][j],f[i-1][j]); // 不買也不賣
		if(i<=w)//如果小于天數，就不能賣
			continue; // 因為第 3，4 種情況都有 i - w - 1，如果 i <= w，會出現負下标
		//在之前的基礎上買
		hh=1,tt=1; // 單調隊列準備
		for(int j=0;j<=m;j++)
		{
			while(hh<tt&&q[hh]<j-as)
				hh++;
			while(hh<tt&&f[i-w-1][q[tt-1]]+q[tt-1]*ap<=f[i-w-1][j]+j*ap)
				tt--;
			q[tt++]=j;
			if(hh<tt)
				f[i][j]=max(f[i][j],f[i-w-1][q[hh]]+q[hh]*ap-j*ap);
		}
		//在之前的基礎上賣
		hh=1,tt=1;
		for(int j=m;j>=0;j--)
		{
			while(hh<tt&&q[hh]>j+bs)
				hh++;
			while(hh<tt&&f[i-w-1][q[tt-1]]+q[tt-1]*bp<=f[i-w-1][j]+j*bp)
				tt--;
			q[tt++]=j;
			if(hh<tt)
				f[i][j]=max(f[i][j],f[i-w-1][q[hh]]+q[hh]*bp-j*bp);
		}
	}
	for(int i=0;i<=m;i++)
		ans=max(ans,f[n][i]);
	cout<<ans<<endl;
	return 0;
}