[SCOI2010]股票交易

题目大意：

网址：https://www.luogu.org/problemnew/show/P2569
大意：在接下来的T天中，每天股票有一个买入价格Api与卖出价格Bpi。
同时，每天买入股票数与卖出股票数分别不能超过Asi与Bsi。
再者，两次股票交易之间时间间隔必须小于W天,任一时刻持股数不能超过MaxP。
那么假设初始时钱数无限，求解T天后的最大收入值（>=0）。
\(0<=W<T<=2000,1<=MaxP<=2000\)

题目解法：

DP，状态太显然了：\(f[i][j]\) 表示到了第i天，持有j股的最大收入额。
转移也很容易：
[1] \(f[i][j] = -1*j*Ap[i] ;(j<=As[i])\) ， 即从当天起直接购买。
[2] \(f[i][j] = f[i-1][j] ;\) ， 即什么都不做。
[3] \(f[i][j] = f[i-W-1][t] - (j-t)*Ap[i];(0<=t<=As[i])\)，即购买股票。
[4] \(f[i][j] = f[i-W-1][t] + (t-j)*Bp[i];(0<=t<=Bs[i])\), 即卖出股票。
直接这样转移的时间复杂度为\(O(N^3)\)的，显然过不去。
发现一个神奇的事情，[3]、[4]可以单调队列优化。
不知道单调队列优化的请戳这里
以优化[3]为例，优化[4]是类似的。
原来的转移方程：\(f[i][j] = f[i-W-1][t] - (j-t)*Ap[i];\)
拆开后移项：\(f[i][j] + Ap[i]*j = f[i-W-1][t] + Ap[i]*t\)
左右两边一模一样，满足单调队列优化要求，大力跑即可。
注意在处理[4]的时候要逆序处理，原因

具体实现代码：

include<bits/stdc++.h>
#define maxn 2005
#define ll long long
#define gi(x) scanf("%lld",&x);
#define INF 1e16+7
using namespace std;
const ll zero = 0;

bool vis[maxn];
ll l1,l2,r1,r2,f[maxn][maxn],T,MaxP,W,Ap,Bp,As,Bs,Ans;

struct Node{ll j,f;};
struct cmp{
    bool operator ()(Node a,Node b){
        return a.f < b.f;}
};
priority_queue<Node,vector<Node>,cmp>Q;

int main(){
    gi(T); gi(MaxP); gi(W);
    for(ll i=0;i<=T;i++)for(ll j=0;j<=MaxP;j++)f[i][j]=-INF;
    f[0][0] = 0;
    for(ll i = 1; i <= T; i ++)
    {
        gi(Ap); gi(Bp); gi(As); gi(Bs);
        ll bf = max(zero,i-W-1);
        for(ll j = 0; j <= MaxP; j ++)
            f[i][j] = f[i-1][j];
        for(ll j = 0; j <= min(MaxP,As); j ++)
            f[i][j] = max(f[i][j] , -1*Ap*j);
        while(!Q.empty())Q.pop();
        for(ll j = 0; j <= MaxP; j ++){
            l1 = max(j-As,zero); r1 = j;
            while(!Q.empty() && !(l1<=Q.top().j && Q.top().j<=r1))Q.pop();
            Q.push((Node){j,f[bf][j] + Ap*j});
            f[i][j] = max(f[i][j],Q.top().f - Ap*j);
        }
        while(!Q.empty())Q.pop();
        for(ll j = MaxP; j >= 0; j --){
            l2 = j; r2 = min(j+Bs,MaxP);
            while(!Q.empty() && !(l2<=Q.top().j && Q.top().j<=r2))Q.pop();
            Q.push((Node){j,f[bf][j] + Bp*j});
            f[i][j] = max(f[i][j],Q.top().f - Bp*j);
        }
    }
    Ans = 0;
    for(ll i = 0; i <= MaxP; i ++)
        Ans = max( Ans , f[T][i] );
    cout<<Ans;
    return 0;
}