https://vjudge.net/problem/HDU-3401
Input
The first line is an integer t, the case number.
The first line of each case are three integers T , MaxP , W .
(0 <= W < T <= 2000, 1 <= MaxP <= 2000) .
The next T lines each has four integers APi，BPi，ASi，BSi( 1<=BPi<=APi<=1000,1<=ASi,BSi<=MaxP), which are mentioned above.
Output
The most money lxhgww can earn.
Sample Input
Sample Output
最近，lxhgww沉迷于股票，经过几天的学习，他发现了一些常规模式。他可以预测未来的T天股市。 在第一天，你可以买价格APi或卖价格BPi的股票。
还有一些其他限制，在一天最多可以买到ASi股票，最多可以卖BSi股票。
两个交易日的间隔应超过W天。 也就是说，假设您在第二天交易（任何买入或卖出股票被视为交易），则下一个交易日必须在第（i + W + 1）天或之后。
而且，任何时候都不能拥有MaxP股票。
在第一天之前，lxhgww已经有无限的钱，但没有股票，当然他想从股票市场赚取尽可能多的钱。 所以问题来了，他能赚多少钱？
大概就是这么道题
这道题首先要构造dp状态转移方程，我们用dp[i][j]来表示第i天，我有j只股票，现在赚了多少钱，为什么这样定义呢，因为如果这样定义，然后转移的话，最后只需要for一遍就知道在最后一天最多盈利了多少
int maxn=-1;
for(int i=1;i<=maxp;i++){
maxn=max(maxn,dp[T][i]);
}
1
2
3
4
那么数组定义出来了，怎么进行状态转移呢
我们发现，每次要计算一个dp[i][j]的时候，都要for从开头到i-W-1这么多天，在每一天，手持k张股票（i<=k <=maxp）而k又要分(k>=j)和(k< j)两种情况，因为要讨论是买入还是卖出，还要讨论是不是什么操作都不做，怎么办，好烦啊，代码复杂度也大，时间复杂度也完全不能承受啊啊啊，大概是O（T* T* maxp* maxp）
所以我们来想一下优化方案，因为题目的限制，交易（py）了一次之后，只能在W天之后才能进行交易（交易之后需要休息嘛）所以我们是否可以只讨论W天之前的状态呢，或许可以，但是题目又允许什么都不干啊，我说不定已经W+n天没有交易了（饥渴），那怎么办呢，我们这个时候再新加一个状态转移
dp[i][j]=max(dp[i][j],dp[i-1][j]);
1
也就是说，我在第i天和第i-1天的时候手持的股票是一样多了，也就是没有买，也没有卖，所以我的i-W-1天是从i-W-2天转移过来的，所以就不用考虑之前的有没有py了嘛，因为已经考虑过啦
那么既然我们只用考虑第i-W-1天的状态了，另外两个（决定第i天是买进还是卖出的）方程也就很好写出来了
dp[i][j]=max(dp[i-W-1][k]-(j-k)*ap[i],dp[i][j]);
//这是买进(1<=k<j)
dp[i][j]=max(dp[i-W-1][k]+(k-j)*bp[i],dp[i][j]);
//这是卖出(j<k<maxp)
1
2
3
4
我在这里解释一下这两个方程
第i天拥有j只股票赚的钱，等于第(i-W-1)天拥有k只股票，然后在第i天购入（j-k）只股票，当然这里的k需要枚举，假如我i-W-1天有一些钱（可以理解为盈利），然后我在第i天进行了一次买入操作，就花掉了一些钱，与其他情况进行比较（比如我在第i-W-1天买了一些股票（钱先变少了），然后在这一天卖出去），此时需要减去一个花费，也就是我买入股票的价格乘以买的只数，注意这里要满足两个条件，第一个条件是购买的数量不能超过当日最多购买的数量（如果超过了的话，就不能进行这次的更新操作，可以直接continue掉，因为是不可能从dp[i-W-1][k]这个状态转移过来的），另外一个就是不要让持的股超过maxp，也就是j不能超过maxp
满足这两个条件的情况下，进行max操作，卖出是同理的，在第i-W-1天拥有了k只股票，然后卖出k-j只股票，用之前的dp数组的值再加上在第i天卖出k-j只股票盈利的钱，就是这个状态转移过来的值，然后进行更新操作即可
复杂度成功降到少了一个T，很成功，很不错，但是还是要T掉啊，怎么办…w…
这个时候必须再想优化，可是好像已经没有什么可以直接通过更改转移方程的方式优化了，怎么办啊，于是我们想到了用单调队列，用一个单调队列来简化我们要进行maxp次操作的更新，直接找出最大值，然后更新即可
我们再观察一下dp转移方程
dp[i][j]=max(dp[i-W-1][k]-(j-k)*ap[i],dp[i][j]);
//这是买进(1<=k<j)
dp[i][j]=max(dp[i-W-1][k]+(k-j)*bp[i],dp[i][j]);
//这是卖出(j<k<maxp)
1
2
3
4
如果是买进
dp[i][j]其实是要与（dp[i-w-1][k]-j* ap[i]+k* ap[i]）在枚举完所有的k值之后取得的最大值比较最大值进行更新
而dp[i-w-1][k]是一个在k确定的情况下已经确定的值，j*ap[i]也是一个直接确定的值，k*ap[i]是一个在k确定的情况下已经确定的值，其中dp[i-w-1][k]和k*ap[i]和k有关，剩下一个根本就和k无关，这个时候相当于是k在往后推，所以就把dp[i-w-1][k]+k* ap[i]用单调队列来维护就行了
对于每次枚举j的操作，如果是买的话，就建一个单调队列来维护dp[i-W-1][k]+k*ap[i]的最大值，注意，如果是买的话，那么有一个条件，即j减去队首的持有股票，如果大于了每天能买的股票，就把队首指针++；这里就是之前讨论的两个条件之一
对于卖的话，也是维护最大值，只是队首的股票减去我们的j如果大于了第i天最多能卖的股票，就将队首指针++；
无论是买还是卖的队首合法性判断，都用while来写
注意一个问题，如果要满足dp的原理，也就是当前状态是从之前的状态推到之后的状态，我们在买和卖的时候，for的顺序是不一样的，当我们买的时候，需要k小于j的状态都已经计算过了，所以正向for循环，当我们卖的时候需要k大于j的状态已经计算过了，所以反向for循环
最后注意一下初始化问题就好了，因为前W天，我如果买的话，不能进行卖的操作，如果不买的话，我就没有股票，所以不能进行卖的操作，所以这个时候进行初始化，是不能进行卖出操作的
可以用一个结构体来表示这个单调队列，存储值和该状态持有的股票
http://www.voidcn.com/article/p-hbfxiyoe-bca.html
题意：炒股……规定每天最多买进多少，卖出多少，并且每次炒股后隔w天才能再次炒股，问最大收益。
思路：
首先想到最朴素的dp。dp[i][j]代表第i天有j股会带来最大收益。
则dp[i][j] = max(dp[i-1][j], dp[r][k]-(j-k)ap[i], dp[r][k]+(k-j)bp[i]); 复杂度是O(T*T*Maxp*Maxp)。
首先想到第一步优化，前面式子r范围是0~i-w-1，怎么优化呢，因为dp[i][j]至少为dp[i-1][j]，那么dp[i-w-1][k] >= dp[...][k]恒成立（...指r的范围内的数）
故dp[i][j] = max(dp[i-1][j], dp[i-w-1][k]-(j-k)ap[i], dp[i-w-1][k]+(k-j)bp[i]); 复杂度是O(T*Maxp*Maxp)。还是很大。
接下来就是单调队列的作用了，dp[i][j] = max(dp[i-1][j], (dp[i-w-1][k]+k*ap[i])-j*ap[i], (dp[i-w-1][k]+k*bp[i])-j*bp[i]);
Recently, lxhgww is addicted to stock, he finds some regular patterns after a few days' study.
He forecasts the next T days' stock market. On the i'th day, you can buy one stock with the price APi or sell one stock to get BPi.
There are some other limits, one can buy at most ASi stocks on the i'th day and at most sell BSi stocks.
Two trading days should have a interval of more than W days. That is to say, suppose you traded (any buy or sell stocks is regarded as a trade)on the i'th day, the next trading day must be on the (i+W+1)th day or later.
What's more, one can own no more than MaxP stocks at any time.
Before the first day, lxhgww already has infinitely money but no stocks, of course he wants to earn as much money as possible from the stock market. So the question comes, how much at most can he earn?
He forecasts the next T days' stock market. On the i'th day, you can buy one stock with the price APi or sell one stock to get BPi.
There are some other limits, one can buy at most ASi stocks on the i'th day and at most sell BSi stocks.
Two trading days should have a interval of more than W days. That is to say, suppose you traded (any buy or sell stocks is regarded as a trade)on the i'th day, the next trading day must be on the (i+W+1)th day or later.
What's more, one can own no more than MaxP stocks at any time.
Before the first day, lxhgww already has infinitely money but no stocks, of course he wants to earn as much money as possible from the stock market. So the question comes, how much at most can he earn?
The first line of each case are three integers T , MaxP , W .
(0 <= W < T <= 2000, 1 <= MaxP <= 2000) .
The next T lines each has four integers APi，BPi，ASi，BSi( 1<=BPi<=APi<=1000,1<=ASi,BSi<=MaxP), which are mentioned above.
1 5 2 0 2 1 1 1 2 1 1 1 3 2 1 1 4 3 1 1 5 4 1 1
3
最近，lxhgww沉迷于股票，经过几天的学习，他发现了一些常规模式。他可以预测未来的T天股市。 在第一天，你可以买价格APi或卖价格BPi的股票。
还有一些其他限制，在一天最多可以买到ASi股票，最多可以卖BSi股票。
两个交易日的间隔应超过W天。 也就是说，假设您在第二天交易（任何买入或卖出股票被视为交易），则下一个交易日必须在第（i + W + 1）天或之后。
而且，任何时候都不能拥有MaxP股票。
在第一天之前，lxhgww已经有无限的钱，但没有股票，当然他想从股票市场赚取尽可能多的钱。 所以问题来了，他能赚多少钱？
大概就是这么道题
这道题首先要构造dp状态转移方程，我们用dp[i][j]来表示第i天，我有j只股票，现在赚了多少钱，为什么这样定义呢，因为如果这样定义，然后转移的话，最后只需要for一遍就知道在最后一天最多盈利了多少
int maxn=-1;
for(int i=1;i<=maxp;i++){
maxn=max(maxn,dp[T][i]);
}
1
2
3
4
那么数组定义出来了，怎么进行状态转移呢
我们发现，每次要计算一个dp[i][j]的时候，都要for从开头到i-W-1这么多天，在每一天，手持k张股票（i<=k <=maxp）而k又要分(k>=j)和(k< j)两种情况，因为要讨论是买入还是卖出，还要讨论是不是什么操作都不做，怎么办，好烦啊，代码复杂度也大，时间复杂度也完全不能承受啊啊啊，大概是O（T* T* maxp* maxp）
所以我们来想一下优化方案，因为题目的限制，交易（py）了一次之后，只能在W天之后才能进行交易（交易之后需要休息嘛）所以我们是否可以只讨论W天之前的状态呢，或许可以，但是题目又允许什么都不干啊，我说不定已经W+n天没有交易了（饥渴），那怎么办呢，我们这个时候再新加一个状态转移
dp[i][j]=max(dp[i][j],dp[i-1][j]);
1
也就是说，我在第i天和第i-1天的时候手持的股票是一样多了，也就是没有买，也没有卖，所以我的i-W-1天是从i-W-2天转移过来的，所以就不用考虑之前的有没有py了嘛，因为已经考虑过啦
那么既然我们只用考虑第i-W-1天的状态了，另外两个（决定第i天是买进还是卖出的）方程也就很好写出来了
dp[i][j]=max(dp[i-W-1][k]-(j-k)*ap[i],dp[i][j]);
//这是买进(1<=k<j)
dp[i][j]=max(dp[i-W-1][k]+(k-j)*bp[i],dp[i][j]);
//这是卖出(j<k<maxp)
1
2
3
4
我在这里解释一下这两个方程
第i天拥有j只股票赚的钱，等于第(i-W-1)天拥有k只股票，然后在第i天购入（j-k）只股票，当然这里的k需要枚举，假如我i-W-1天有一些钱（可以理解为盈利），然后我在第i天进行了一次买入操作，就花掉了一些钱，与其他情况进行比较（比如我在第i-W-1天买了一些股票（钱先变少了），然后在这一天卖出去），此时需要减去一个花费，也就是我买入股票的价格乘以买的只数，注意这里要满足两个条件，第一个条件是购买的数量不能超过当日最多购买的数量（如果超过了的话，就不能进行这次的更新操作，可以直接continue掉，因为是不可能从dp[i-W-1][k]这个状态转移过来的），另外一个就是不要让持的股超过maxp，也就是j不能超过maxp
满足这两个条件的情况下，进行max操作，卖出是同理的，在第i-W-1天拥有了k只股票，然后卖出k-j只股票，用之前的dp数组的值再加上在第i天卖出k-j只股票盈利的钱，就是这个状态转移过来的值，然后进行更新操作即可
复杂度成功降到少了一个T，很成功，很不错，但是还是要T掉啊，怎么办…w…
这个时候必须再想优化，可是好像已经没有什么可以直接通过更改转移方程的方式优化了，怎么办啊，于是我们想到了用单调队列，用一个单调队列来简化我们要进行maxp次操作的更新，直接找出最大值，然后更新即可
我们再观察一下dp转移方程
dp[i][j]=max(dp[i-W-1][k]-(j-k)*ap[i],dp[i][j]);
//这是买进(1<=k<j)
dp[i][j]=max(dp[i-W-1][k]+(k-j)*bp[i],dp[i][j]);
//这是卖出(j<k<maxp)
1
2
3
4
如果是买进
dp[i][j]其实是要与（dp[i-w-1][k]-j* ap[i]+k* ap[i]）在枚举完所有的k值之后取得的最大值比较最大值进行更新
而dp[i-w-1][k]是一个在k确定的情况下已经确定的值，j*ap[i]也是一个直接确定的值，k*ap[i]是一个在k确定的情况下已经确定的值，其中dp[i-w-1][k]和k*ap[i]和k有关，剩下一个根本就和k无关，这个时候相当于是k在往后推，所以就把dp[i-w-1][k]+k* ap[i]用单调队列来维护就行了
对于每次枚举j的操作，如果是买的话，就建一个单调队列来维护dp[i-W-1][k]+k*ap[i]的最大值，注意，如果是买的话，那么有一个条件，即j减去队首的持有股票，如果大于了每天能买的股票，就把队首指针++；这里就是之前讨论的两个条件之一
对于卖的话，也是维护最大值，只是队首的股票减去我们的j如果大于了第i天最多能卖的股票，就将队首指针++；
无论是买还是卖的队首合法性判断，都用while来写
注意一个问题，如果要满足dp的原理，也就是当前状态是从之前的状态推到之后的状态，我们在买和卖的时候，for的顺序是不一样的，当我们买的时候，需要k小于j的状态都已经计算过了，所以正向for循环，当我们卖的时候需要k大于j的状态已经计算过了，所以反向for循环
最后注意一下初始化问题就好了，因为前W天，我如果买的话，不能进行卖的操作，如果不买的话，我就没有股票，所以不能进行卖的操作，所以这个时候进行初始化，是不能进行卖出操作的
可以用一个结构体来表示这个单调队列，存储值和该状态持有的股票
http://www.voidcn.com/article/p-hbfxiyoe-bca.html
题意：炒股……规定每天最多买进多少，卖出多少，并且每次炒股后隔w天才能再次炒股，问最大收益。
思路：
首先想到最朴素的dp。dp[i][j]代表第i天有j股会带来最大收益。
则dp[i][j] = max(dp[i-1][j], dp[r][k]-(j-k)ap[i], dp[r][k]+(k-j)bp[i]); 复杂度是O(T*T*Maxp*Maxp)。
首先想到第一步优化，前面式子r范围是0~i-w-1，怎么优化呢，因为dp[i][j]至少为dp[i-1][j]，那么dp[i-w-1][k] >= dp[...][k]恒成立（...指r的范围内的数）
故dp[i][j] = max(dp[i-1][j], dp[i-w-1][k]-(j-k)ap[i], dp[i-w-1][k]+(k-j)bp[i]); 复杂度是O(T*Maxp*Maxp)。还是很大。
接下来就是单调队列的作用了，dp[i][j] = max(dp[i-1][j], (dp[i-w-1][k]+k*ap[i])-j*ap[i], (dp[i-w-1][k]+k*bp[i])-j*bp[i]);
对于每一个j。j*ap[i]或j*bp[i]相同。所以取其前或后的(dp[i-w-1][k]+k*ap[i])或(dp[i-w-1][k]+k*bp[i])的最大值就行。最大值用单调队列维护
