形式化题目？
原题链接（没有格式化）
模型及定义
一眼锁 DP （这个只能靠做题感觉），考虑如何设置状态：
- 一维，显然天数 \(i\) 一定得放进去
- 二维，发现题目有一个很特别的限制：至多股票数量。如果正常转移，我们我发保证股票数量的正确性，所以把股票个数 \(j\) 放进去
算法推导
模型搭建
直接考虑状态转移方程。首先，对于一天，我们有两个操作：1.买股票 2.卖股票。所以按照买与卖的方式排列会有三种可能：1. 第一次买 2.之前已经交易过了，现在我要买 3.之前已经交易过了，现在我要卖。
注意：别忘了我们可以什么都不干！！
OK，现在我们已经理清楚了所有的可能，那么就把文字转化成代码吧：
- 什么都不干：
不难想到。股票数量不变，直接继承前一天的代价。
f[i][j] = f[i - 1][j];
- 第一次买：
不难想到*2，既然是第一次买，那就需要买的数量乘以单价的代价。
f[i][j] = max(f[i][j], -1 * j * AP[i]);
- 之前已经交易过了，现在我要买：
先给结论（\(k\) 为之前的股票数量）：
f[i][j] = max(f[i][j], f[i - w - 1][k] - (j - k) * AP[i]);
先看代价是如何计算的。现在我的股票数量是 \(j\) ，买之前又是 \(k\) ，所以我买了 \(j-k\) 个股票，花费的代价也就好算了。我们再看为什么一定是从 \(i-w-1\) 天转移，为什么 \(i-w-2\) 就不行呢？那么好，我们假设会有一个天数 \(ni\) 满足： \(ni < i - w - 1~\wedge~f_{ni,k} > f_{i-w,k}\) 。考虑证伪，发现因为有第一种情况，所以对于 \(j\) 相同的递推状态一定是一个单调不下降的序列，故不满足 \(f_{ni,k} > f_{i-w,k}\) ，所以原命题成立。
- 之前已经交易过了，现在我要卖：
根据第三种情况，我们可以知道这次也一定是从第 \(i-w-1\) 天转移过来。根据价格计算的方式，我们能够得到这样的一个代价：\((k-j) \times BP_i\) 。把这些东西拼起来，就能得到：（ \(k\) 表示为之前股票的数量）
f[i][j] = max(f[i][j], f[i - w - 1][k] + (k - j) * BP[i]);
很好，正解出来了，收工
咳咳，聪明的小朋友可以发现时间复杂度有问题哈。。。那么开始 DP 优化了吧
关键步骤：DP优化
主要是看三、四情况，我就用第三种情况举例，第四种情况以此类推：
我们先用乘法分配律拆开式子： \(f_{i,j}=\max(f_{i-w-1,k} + kBP_i - jBP_i)\)
发现项 "\(-jBP_i\)" 与枚举项并不相关，故可提出，变为： \(f_{i,j}=\max(f_{i-w-1,k} + kBP_i) - jBP_i\)
接着，观察 \(\max\) 中的式子，容易发现是一个左端点固定、右端点递增的区间最值，所以可以用单调队列优化时间复杂度。
代码
#include <cstdio>
#include <algorithm>
#include <string>
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int ui;
const int MAXSZ = 1 << 20;
char ch, buf[MAXSZ], cuf[MAXSZ], *p1, *p2;
int C;
#define ge() (p1 == p2 && (p2 = buf + fread(p1 = buf, 1, MAXSZ, stdin), p1 == p2) ? EOF : *p1++)
#define pu(c) (C ^ MAXSZ ? cuf[C ++] = c : (fwrite(cuf, 1, MAXSZ, stdout), cuf[(C = 0) ++] = c))
#define Flush() (fwrite(cuf, 1, C, stdout), C = 0)
#define line() pu('\n')
#define space() pu(' ')
#define I inline
template <typename T_T>
I void read(T_T &x) {x = 0;bool flag = false;while (ch < '0' || '9' < ch) {if (ch == EOF) {Flush();exit(0);}ch = ge(), flag |= (ch == '-');}while ('0' <= ch && ch <= '9') {x = x * 10 + (ch ^ 48);ch = ge();}if (flag) x = -x;
}
bool Ccheck(char cha) {// 此处填判断条件
}
bool Scheck(char cha) {// 此处填判断条件
}
I void cread(char &x) {while (!Ccheck(ch)) {if (ch == EOF) {Flush();exit(0);}ch = ge();}x = ch, ch = ge();
}
I void sread(std::string &str) {str = "";while (!Scheck(ch)) {if (ch == EOF) {Flush();exit(0);}ch = ge();}while (Scheck(ch)) {str += ch;ch = ge();}
}
template <typename T_T>
I void write(T_T x) {if (x < 0) {pu('-');x = -x;}if (x > 9) write(x / 10);pu(x % 10 | 48);
}
template <typename T_T>
I void Write(T_T x, bool flag = true) {write(x);if (flag) line();else space();
}
template <typename T_T>
I T_T max(T_T a, T_T b) { return a > b ? a : b; }
template <typename T_T>
I T_T min(T_T a, T_T b) { return a < b ? a : b; }
template <typename T_T>
I void fmax(T_T &a, T_T b) { a = a > b ? a : b; }
template <typename T_T>
I void fmin(T_T &a, T_T b) { a = a < b ? a : b; }
// 上面都是些无关紧要的东西const int N = 2005, INF = 2e9;
int n, MaxP, w, AP[N], AS[N], BP[N], BS[N]; // 定义皆如题
int f[N][N], q[N], head, tail; // f为dp数组，其他为手写单调队列int main() {// freopen("Ryan.in", "r", stdin);// freopen("Ryan.out", "w", stdout);read(n), read(MaxP), read(w);for (int i = 1; i <= n; i++)read(AP[i]), read(BP[i]), read(AS[i]), read(BS[i]);for (int j = 0; j <= MaxP; j++) f[0][j] = -INF; // 初始化for (int i = 1; i <= n; i++) {for (int j = 0; j <= MaxP; j++) { // 第一、二中情况if (j <= AS[i]) f[i][j] = -1 * AP[i] * j;else f[i][j] = -INF;fmax(f[i][j], f[i - 1][j]);}if (i <= w) continue ; // 如果“没有前一天”，则跳过// 单调队列正常更新，按照之前推得式子进行判断head = 1, tail = 0;for (int j = 0; j <= MaxP; j++) {while (head <= tail && q[head] < j - AS[i]) ++ head; // 过时了while (head <= tail && f[i - w - 1][q[tail]] + q[tail] * AP[i] <= f[i - w - 1][j] + j * AP[i]) -- tail; // 不比新来的优q[++ tail] = j;if (head <= tail) fmax(f[i][j], f[i - w - 1][q[head]] + (q[head] - j) * AP[i]); // 更新}// 同理head = 1, tail = 0;for (int j = MaxP; j >= 0; j--) {while (head <= tail && q[head] > j + BS[i]) ++ head;while (head <= tail && f[i - w - 1][q[tail]] + q[tail] * BP[i] <= f[i - w - 1][j] + j * BP[i]) -- tail;q[++ tail] = j;if (head <= tail) fmax(f[i][j], f[i - w - 1][q[head]] + (q[head] - j) * BP[i]);}}Write(f[n][0]); // 答案一定是剩0个股票，很好想Flush();fclose(stdin); fclose(stdout);return 0;
}
完结撒花~~感谢观看!