传送门：点击打开链接
题意：有种股票，现在知道n天，拥有的股票股数必须<=V,每两次操作时间之差必须大于W。接下来n天，分别是当天股票买和卖的价格，以及买和卖的最大上限。刚开始认为钱是INF的，问最后能赚多少钱。
思路：一道非常好的单调队列优化dp的好题！
首先，dp无非就两种设法,
1.dp[i][j]表示最后一次操作为第i天，已经拥有了j只股票的赚的最大钱数.
2.dp[i][j]前i天里，已经拥有了j只股票的赚的最大钱数.
我们可以发现，如果是第一种设法，方程不好转移，所以我们采用第二种，那么很容易就能列出方程
对于i>=W+2
dp[i][j]=dp[i-1][j]
买股票 dp[i][j]=max(dp[i][j],dp[i-W-1][k]+k*AP[i])-j*AP[i], j-k<=AS[i]
卖股票 dp[i][j]=max(dp[i][j],dp[i-W-1][k]+k*BP[i])-j*BP[i], j-k<=BS[i]
所以，买股票的时候j的循环应该是从小到大，卖股票的时候循环应该是从大到小。
然后我们继续来考虑i>=W+2的时候，对于单调队列添加起点的边界考虑。
买股票的时候，我们把j=0添加到单调队列中，卖股票的时候，我们把j=V添加到单调队列中
对于比较复杂的方程，有时候单纯的用单调队列只记录位置，就会显得有点笨重，这里我是采用了结构体，这样可以使得代码更加清晰，而且方便维护。
这题还有另外一个边界，那就是1<=i<=W+1的情况
dp[i][j]=j<=AS[i]?-j*AP[i]:-INF;
if(i>1) dp[i][j]=max(dp[i][j],dp[i-1][j]);
if(i>1) dp[i][j]=max(dp[i][j],dp[i-1][j]);
这个怎么理解呢，因为当i在这个区间的时候，肯定只能取到某一天。
然后对于j>AS[i]的情况，因为第i天实在买不了j只股票，所以这个状态是达不到的，我们记为-INF
其次就是最容易错的那句if语句，因为我们的dp的意义，并不是以第i天为最后一天操作时的赚的最大钱数，而是前i天！
所以我们应该还要考虑这天不选的情况，所以还应该考虑只从前面的状态转移过来时的情况
总的来说，我觉得这题有几个地方都很适合总结。
一个是dp的两种设法，以后要习惯性的想到，不能死扣一种。
第二个就是关于dp的边界，一定要结合dp的含义想清楚再写，否则很有可能调试不出来。
第三个就是单调队列的初始边界，一般是把第一个状态直接加入进去，然后for循环从第二个状态开始
#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<stack>
#include<queue>
#include<cstdio>
#include<cctype>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define fuck(x) cout<<"["<<x<<"]"
#define FIN freopen("input.txt","r",stdin)
#define FOUT freopen("output.txt","w+",stdout)
using namespace std;
typedef long long LL;
typedef pair<int, int>PII;const int MX = 2e3 + 5;
const int INF = 0x3f3f3f3f;int n, V, W;
int dp[MX][MX];
int c, r;
int AP[MX], BP[MX], AS[MX], BS[MX];void umax(int &a, int b) {a = a > b ? a : b;
}struct Data {int id, x;Data() {}Data(int _id, int _x) {id = _id; x = _x;}
} Q[MX];int solve() {for(int i = 1; i <= W + 1; i++) {for(int j = 0; j <= V; j++) {dp[i][j] = j <= AS[i] ? -j * AP[i] : -INF;if(i > 1) umax(dp[i][j], dp[i - 1][j]);}}for(int i = W + 2; i <= n; i++) {for(int j = 0; j <= V; j++) {dp[i][j] = dp[i - 1][j];}c = r = 0; Q[r++] = Data(0, dp[i - W - 1][0]);for(int j = 1; j <= V; j++) {while(c < r && j - Q[c].id > AS[i]) c++;int Max = Q[c].x;umax(dp[i][j], Max - j * AP[i]);Data temp(j, dp[i - W - 1][j] + j * AP[i]);while(c < r && Q[r - 1].x < temp.x) r--;Q[r++] = temp;}c = r = 0; Q[r++] = Data(V, dp[i - W - 1][V] + V * BP[i]);for(int j = V - 1; j >= 0; j--) {while(c < r && Q[c].id - j > BS[i]) c++;int Max = Q[c].x;umax(dp[i][j], Max - j * BP[i]);Data temp(j, dp[i - W - 1][j] + j * BP[i]);while(c < r && Q[r - 1].x < temp.x) r--;Q[r++] = temp;}}return dp[n][0];
}int main() {int T; //FIN;scanf("%d", &T);while(T--) {scanf("%d%d%d", &n, &V, &W);for(int i = 1; i <= n; i++) {scanf("%d%d%d%d", &AP[i], &BP[i], &AS[i], &BS[i]);}printf("%d\n", solve());}return 0;
}