股票交易

题目传送门

解题思路

通过一位巨佬的洛谷博客解出来的
用dp+单调队列优化

AC代码

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int T,Maxp,w,ap,bp,as,bs,head,tail,p[2005],f[2005][2005];
int main()
{
   
    cin>>T>>Maxp>>w;
    memset(f,128,sizeof(f)); 
    for(int i=1;i<=T;i++)
	{
   
        cin>>ap>>bp>>as>>bs;
        for(int j=0;j<=as;j++)f[i][j]=-1*j*ap;//未买股票的状态下买股票
        for(int j=0;j<=Maxp;j++)f[i][j]=max(f[i][j],f[i-1][j]);//不买也不卖 
        if(i<=w)continue;//因为下面都要i-w-1
        head=1;//初值
        tail=0;
        for(int j=0;j<=Maxp;j++)//第三种状态（在之前的基础上买股票）
		{
   
			while(f[i-w-1][p[tail]]+p[tail]*ap<=f[i-w-1][j]+j*ap&&head<=tail)tail--;//单调队列（顺序） 
            p[++tail]=j; 
			while(p[head]<j-as&&head<=tail)head++; 
            if(head<=tail)f[i][j]=max(f[i][j],f[i-w-1][p[head]]+p[head]*ap-j*ap);//状态转移 
        }
        head=1;//初值
        tail=0;
        for(int j=Maxp;j>=0;j--)//第四种状态（在之前的基础上卖股票）
		{
   
            while(f[i-w-1][p[tail]]+p[tail]*bp<=f[i-w-1][j]+j*bp&&head<=tail)tail--;//单调队列（逆序）
            p[++tail]=j;
			while(p[head]>j+bs&&head<=tail)head++;
            if(head<=tail)f[i][j]=max(f[i][j],f[i-w-1][p[head]]+p[head]*bp-j*bp);//状态转移
        }
    }
    int s=0;
    for(int i=0;i<=Maxp;i++)//找最大
     s=max(s,f[T][i]);
    cout<<s; 
}

谢谢