原题链接

1 题目

1.1 题目所需求出内容

对于本题，最终要求：一个最小值

1.2 题目背景、允许、禁止与限制

背景：
有 $T$ 天，第 $i$ 天的股票买入价为每股 $AP_i$ 元，卖出价为每股 $BP_i$ 元
允许：
每天可以选择买入 或 卖出（二选一）
求能赚的钱最多是多少
限制：
在任意两次买入/卖出之间至少间隔 $W$ 天
第 $i$ 天的买入至多 $AS_i$ 股，卖出至多 $BS_i$ 股

1.3 题目数据范围与猜测

$1 \le T \le 2000，MaxP \le 2000 \longrightarrow O(T·MaxP)$

1.4 一句话概括题意

每天可选择买入或卖出（有限制），求最多钱数

2 题目破题推导

2.1 第一步：分情况讨论

对于第 $i$ 天，无非就四种选项

• 从 $0$ 到 $AS_i$ 尝试买不同个数的股票
• 什么也不做
• 买入股票（最起码从 $i - w - 1$ 及其以前的天的情况开始考虑）
• 卖出股票（仍然是最起码从 $i - w - 1$ 及其以前的天的情况开始考虑）

2.2 第二步：数学·分离思想（结合单调队列实现）

很明显的 $\huge{dp}$

step1:
想一下dp定义：$dp[i][j]$ 代表第 $i$ 天持有 $j$ 股股票时的最大收益

step2:
$k$ 表示第 $i-w-1$ 天结束后，手里持有的股票数量
$j$ 表示第 $i$ 天结束后手里持有的股票数量
那么转移方程（对于分情况讨论的前两种情况太简单，而且无法优化，就不在这里讨论）
买入：$dp[i][j] = max(dp[i-w-1][k] + k * ap - j * ap)~~~其中 j - as \le k \le j$
卖出：$dp[i][j] = max(dp[i-w-1][k] + k * bp - j * bp)~~~~其中 j \le k \le j + bs$
发现 $O(T·MaxP^2)$ 超时，所以要用单调队列优化

step3:
数学分离变量
把只和 $k(第i-w-1天结束后，手里持有的股票数量)$ 有关的和只和 $j(第i天结束后手里持有的股票数量)$拆分开来
把最优的 $k$ 转移到这次的 $j$ 上
买入：$dp[i][j] = (dp[i-w-1][k] + k * ap) - j * ap$
卖出：$dp[i][j] = (dp[i-w-1][k] + k * bp) - j * bp$
此时括号内只含起点 $k$ 的信息，外面的 -j * ap（或 -j * bp）对所有候选 $k$ 都是固定常数

step4:
接下来就是单调队列维护 $dp[i-w-1][k] + k * ap$ 的最大值

step5:
队头过期处理：
因为买入时合法 $k$ 的范围是 $[j-as,j]$，卖出时是 $[j,j+bs]$
所以队头 $q[head]$ 凡是不合法的都弹出
为什么不是 $dp[q[head]]$？因为 $k$ 只和下标有关（持有量），和最大价值无关

step6:
我们刚刚只说了买入的，卖出其实同理，把和A有关的替换成B即可

3 模型匹配

上方已经基本讲解

4 最终代码（禁止抄袭，仅用于参考）

#include <bits/stdc++.h>
using namespace std;

int t, maxp, w;
const int N = 2222;
int dp[N][N];
int l, r, q[N];
const int INF = 0x3f3f3f3f;
int ap, bp, as, bs;

int main(){

    cin >> t >> maxp >> w;
    memset(dp, -0x3f, sizeof(dp));
    for (int i = 1;i <= t;i++){
        cin >> ap >> bp >> as >> bs;
        for (int j = 0;j <= as;j++){
            dp[i][j] = -j * ap;
        }
        for (int j = 0;j <= maxp;j++){
            dp[i][j] = max(dp[i][j], dp[i - 1][j]);
        }
        if (i <= w) continue;
        l = 1, r = 0;
        for (int j = 0;j <= maxp;j++){
            while(l <= r && q[l] < j - as){
                l++;
            }
            while(l <= r && dp[i - w - 1][q[r]] + q[r] * ap <= dp[i - w - 1][j] + j * ap){
                r--;
            }
            q[++r] = j;
            if (l <= r){
                dp[i][j] = max(dp[i][j], dp[i - w - 1][q[l]] + q[l] * ap - j * ap);
            }
        }
        l = 1, r = 0;
        for (int j = maxp;j >= 0;j--){
            while(l <= r && q[l] > j + bs){
                l++;
            }
            while(l <= r && dp[i - w - 1][q[r]] + q[r] * bp <= dp[i - w - 1][j] + j * bp){
                r--;
            }
            q[++r] = j;
            if (l <= r){
                dp[i][j] = max(dp[i][j], dp[i - w - 1][q[l]] + q[l] * bp - j * bp);
            }
        }
    }
    int mx = INT_MIN;
    for (int i = 0;i <= maxp;i++){
        mx = max(mx, dp[t][i]);
    }
    cout << mx;
    
    return 0;
}