股票交易
题目传送门
解题思路
通过一位巨佬的洛谷博客解出来的
用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-1head=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;
}