股票交易[单调队列优化DP]

本文主要是介绍股票交易[单调队列优化DP]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门

我们用f[i][j] 表示交易到第i天,手上有j个股票的最大收益

对于买入

变一下形

单调队列维护min中的一坨就可以了

---

#include<bits/stdc++.h>
#define N 5005
using namespace std;
int f[N][N];
int T,P,w;
int a[N],b[N] , c[N],d[N];
int q[N];
int main(){//freopen("1.in","r",stdin);scanf("%d%d%d",&T,&P,&w);memset(f,-63,sizeof(f)); f[0][0]=0;for(int i=1;i<=T;i++){scanf("%d%d%d%d",&a[i],&b[i],&c[i],&d[i]);}for(int i=1;i<=T;i++){for(int j=0;j<=c[i];j++) f[i][j] = -j*a[i];for(int j=0;j<=P;j++) f[i][j] = max(f[i][j] , f[i-1][j]);if(i<=w) continue;int x=i-w-1; int l=1,r=0;for(int j=0;j<=P;j++){while(l<=r && j-q[l] > c[i]) l++;while(l<=r && f[x][j] + j*a[i] >= f[x][q[r]] + q[r]*a[i]) r--;q[++r] = j;if(l<=r) f[i][j] = max(f[i][j] , f[x][q[l]] - (j-q[l])*a[i]); } l=1,r=0;for(int j=P;j>=0;j--){while(l<=r && q[l]-j > d[i]) l++;while(l<=r && f[x][j] + j*b[i] >= f[x][q[r]] + q[r]*b[i]) r--;q[++r] = j;if(l<=r) f[i][j] = max(f[i][j] , f[x][q[l]] - (j-q[l])*b[i]);}}printf("%d",f[T][0]); return 0;
}

 

这篇关于股票交易[单调队列优化DP]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---