难度：省选/NOI-

题目描述

        最近lxhgww 又迷上了投资股票，通过一段时间的观察和学习，他总结出了股票行情的一些规律。
        通过一段时间的观察，lxhgww 预测到了未来$T$天内某只股票的走势，第$i$天的股票买入价为每股$AP_i$，第$i$天的股票卖出价为每股$BP_i$（数据保证对于每个$i$，都有 $AP_i \geq BP_i$），但是每天不能无限制地交易，于是股票交易所规定第$i$天的一次买入至多只能购买$AS_i$股，一次卖出至多只能卖出$BS_i$股。
        另外，股票交易所还制定了两个规定。为了避免大家疯狂交易，股票交易所规定在两次交易（某一天的买入或者卖出均算是一次交易）之间，至少要间隔$W$天，也就是说如果在第$i$天发生了交易，那么从第$i+1$天到第$i+W$天，均不能发生交易。同时，为了避免垄断，股票交易所还规定在任何时间，一个人的手里的股票数不能超过$MaxP$。
        在第1天之前，lxhgww 手里有一大笔钱（可以认为钱的数目无限），但是没有任何股票，当然$T$天以后，lxhgww 想要赚到最多的钱，聪明的程序员们，你们能帮助他吗？

输入输出格式

输入格式：

        输入数据第一行包括3个整数，分别是 $T$，$MaxP$，$W$。
        接下来$T$行，第$i$行代表第$i-1$天的股票走势，每行4个整数，分别表示 $AP_i,BP_i,AS_i,BS_i$。

输出格式：

        输出数据为一行，包括1个数字，表示lxhgww 能赚到的最多的钱数。

输入输出样例

Sample input

5 2 0
2 1 1 1
2 1 1 1
3 2 1 1
4 3 1 1
5 4 1 1

Sample output

3

说明

        对于$30\%$的数据，$0\leq W<T\leq 50,1\leq MaxP≤50$
        对于$50\%$的数据，$0\leq W<T\leq 2000,1\leq MaxP≤50$
        对于$100\%$的数据，$0\leq W<T\leq 2000,1\leq MaxP≤2000$
        对于所有的数据，$1\leq BP_i\leq AP_i\leq 1000,1\leq AS_i,BS_i\leq MaxP$

题解

        常规的动态规划题。定义$dp(i,j)$为当前拥有j股，在i~T天能够得到的最大收益，那么有状态转移方程：
        第i天交易时：

        不交易时：

        其实就是枚举第i天可以买入或卖出的股票数目然后转移。参数需要满足以下制约条件：

        同一天不可能同时买入和卖出（由于$AP_i \geq BP_i$的存在，一定不最优），故分别考虑即可。先来看第i天买入的情况。

        DP本身的复杂度为$O(TMaxP)$，转移复杂度为$O(MaxP)$，总复杂度$O(TMaxp^2)$，显然不可取，需要优化。
        将DP方程改成下面的形式：

        注意到x的区间左右端点都是单调不减的，且max中的取值与j没有关系，那么就可以使用单调队列优化，将总复杂度降到$O(TMaxP)$。同理，卖出也可以写成：

        加单调队列后，复杂度降维，本题就被切掉了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<bits/stdc++.h>

using namespace std;

inline int read() {
    char e = getchar();
    int s = 0;
    while (e < '-')e = getchar();
    while (e > '-')s = (s << 1) + (s << 3) + (e & 15), e = getchar();
    return s;
}

deque<int> dq1, dq2;
int T, MaxP, W, AP[2005], BP[2005], AS[2005], BS[2005], dp[2005][2005], now1, now2;

inline void add1(int i, int j) {
    while (!dq1.empty() && -AP[i] * j + dp[i + W + 1][j] > -AP[i] * dq1.back() + dp[i + W + 1][dq1.back()])
        dq1.pop_back();
    dq1.push_back(j);
}

inline int f1(int j) {
    while (dq1.front() < j)dq1.pop_front();
    return dq1.front();
}

inline void add2(int i, int j) {
    while (!dq2.empty() && -BP[i] * j + dp[i + W + 1][j] > -BP[i] * dq2.back() + dp[i + W + 1][dq2.back()])
        dq2.pop_back();
    dq2.push_back(j);
}

inline int f2(int j) {
    while (dq2.front() < j)dq2.pop_front();
    return dq2.front();
}

int main() {
    T = read(), MaxP = read(), W = read();
    for (int i = 1; i <= T; i++)AP[i] = read(), BP[i] = read(), AS[i] = read(), BS[i] = read();
    for (int i = 0; i <= MaxP; i++)dp[T][i] = min(i, BS[T]) * BP[T];
    for (int i = T - 1; i >= 1; i--) {
        dq1.clear(), dq2.clear(), now1 = 0, now2 = max(1 - BS[i], 0) - 1;
        for (int j = 0; j <= MaxP; j++) {
            if (i + W >= T)dp[i][j] = max(dp[i + 1][j], min(j, BS[i]) * BP[i]);
            else {
                if (j != MaxP) {
                    for (int ss = now1 + 1; ss <= min(MaxP, AS[i] + j); ss++)add1(i, ss), now1 = ss;
                    dp[i][j] = max(dp[i][j], j * AP[i] - AP[i] * f1(j + 1) + dp[i + W + 1][f1(j + 1)]);
                }
                if (j != 0) {
                    for (int ss = now2 + 1; ss <= j - 1; ss++)add2(i, ss), now2 = ss;
                    dp[i][j] = max(dp[i][j],
                                   j * BP[i] - BP[i] * f2(max(j - BS[i], 0)) + dp[i + W + 1][f2(max(j - BS[i], 0))]);
                }
                dp[i][j] = max(dp[i][j], dp[i + 1][j]);
            }
        }
    }
    cout << max(0, dp[1][0]);
    return 0;
}