股票交易

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 2603 字
T天，每天买/卖价AP/BP、限购量AS/B
一本通
练习
正文

/*
原题：T1605 「一本通 5.5 练习 4」股票交易
题意：T 天，每天买/卖价 AP/BP、限购量 AS/BS，任意时刻持股 ≤MaxP，两次交易间隔 ≥W 天；
     初始钱无限、持股 0，求 T 天后最大收益。
思路：dp[i][j] 为第 i 天持 j 股的最大现金。不交易继承 dp[i-1][j]；
     买/卖用单调队列在窗口 AS/BS 内优化：买 dp+=max(g[k]+(k-j)AP)，卖 dp+=max(g[k]+(k-j)BP)，
     其中 g 取参考日 i-W-1 的状态（冷却 W 天）。首段以 dp[0][0]=0 为基准。
复杂度：时间 O(T·MaxP)，空间 O(T·MaxP)。
易错点：交易参考日取 i-W-1；首段用 dp[0][0]=0 作基准；答案为末日所有持股态最大值；
     卖队列 j 递减，须先算候选再 push 当前 j（且窗口只 pop 越界 front>j+BS），否则卖出永不触发。
*/
#include <bits/stdc++.h>
using namespace std;
const long long INF=1e18;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T,MaxP,W;
    cin>>T>>MaxP>>W;
    vector<int> AP(T+1),BP(T+1),AS(T+1),BS(T+1);
    for(int i=1;i<=T;i++){
        cin>>AP[i]>>BP[i]>>AS[i]>>BS[i];
    }
    vector<vector<long long>> dp(T+1,vector<long long>(MaxP+1,-INF));
    dp[0][0]=0;
    for(int i=1;i<=T;i++){
        int prev=i-W-1;
        for(int j=0;j<=MaxP;j++){
            dp[i][j]=dp[i-1][j];
        }
        // 参考状态 g：prev>=0 用 dp[prev]，否则仅 0 股可行且现金 0
        vector<long long> g(MaxP+1,-INF);
        if(prev>=0){
            for(int j=0;j<=MaxP;j++){
                g[j]=dp[prev][j];
            }
        }else{
            g[0]=0;
        }
        // 买入：dp[i][j]=max(dp[i][j], g[k]+(k-j)·AP)，k∈[j-AS,j-1]
        deque<int> q;
        for(int j=0;j<=MaxP;j++){
            while(!q.empty()&&q.front()<j-AS[i]){
                q.pop_front();
            }
            if(!q.empty()){
                long long cand=g[q.front()]+(q.front()-j)*(long long)AP[i];
                if(cand>dp[i][j]){
                    dp[i][j]=cand;
                }
            }
            while(!q.empty()&&g[q.back()]+q.back()*(long long)AP[i]<=g[j]+j*(long long)AP[i]){
                q.pop_back();
            }
            q.push_back(j);
        }
        // 卖出：dp[i][j]=max(dp[i][j], g[k]+(k-j)·BP)，k∈[j+1,j+BS]
        // 先以队列中“更大持股 m>k>j”的已入队状态算候选，再把当前 j 入队供更小的 j 复用
        deque<int> q2;
        for(int j=MaxP;j>=0;j--){
            while(!q2.empty()&&q2.front()>j+BS[i]){
                q2.pop_front();
            }
            if(!q2.empty()){
                long long cand=g[q2.front()]+(q2.front()-j)*(long long)BP[i];
                if(cand>dp[i][j]){
                    dp[i][j]=cand;
                }
            }
            while(!q2.empty()&&g[q2.back()]-q2.back()*(long long)BP[i]<=g[j]-j*(long long)BP[i]){
                q2.pop_back();
            }
            q2.push_back(j);
        }
    }
    long long ans=-INF;
    for(int j=0;j<=MaxP;j++){
        ans=max(ans,dp[T][j]);
    }
    cout<<ans<<'\n';
    return 0;
}
股票交易

正文

一本通·提高篇的其它内容
