Description

最近 lxhgww 又迷上了投资股票, 通过一段时间的观察和学习, 他总结出了股票行情的一些 规律. 通过一段时间的观察, lxhgww 预测到了未来 \(T\) 天内某只股票的走势, 第 \(i\) 天的 股票买入价为每股 \(APi\), 第 \(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 想要赚到最多的钱, 聪明的程序员们, 你们能帮助他吗?

Input

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

Output

输出数据为一行, 包括 \(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

Data Range

对于 30% 的数据,\(0 \leq W \lt T \leq 50, 1 \leq MaxP \leq 50\)

对于 50% 的数据,\(0 \leq W \lt T \leq 2000, 1 \leq MaxP \leq 50\)

对于 100% 的数据,\(0 \leq W \lt T \leq 2000, 1 \leq MaxP \leq 2000\)

对于所有的数据,\(1 \leq BP_i \leq AP_i \leq 1000, 1 \leq AS_i, BS_i \leq MaxP\)

Explanation

膜巨神题解:http://blog.csdn.net/qpswwww/article/details/44489417

很显然是个 DP 题, 比较容易想到下面的 DP 做法:

用 \(f[i][j]\) 表示第 \(i\) 天, 手上有 \(j\) 个股票的最大获利. 显然最终的答案为 \(max\{f[i][0]\}\) (显然以某天交易结束后收手不干, 肯定是手上没有股票是最优的), DP 初始化如下:

\[f(x) = \left\{ \begin{aligned} f[i][j] = max\{f[i - 1][j], - a_{pj}\}, j \leq a_s(第i天没买或全是这天买的)\\ f[i][j] = f[i - 1][j], j \gt a_s (手上股票超出了一次购买的限制，只能是第i天没买)\\ \end{aligned} \right.\]

而 DP 方程则为 (以转移情况为购入股票举例)

\[f[i][j] = max\{f[i - w - 1][k] + a_p \cdot (j - k)\}\]

这样做的正确性是显然的,\(f[i][j]\) 一定是前 \(i\) 天里手持 \(j\) 股的最优解, 这样一来 我们就节省了一维时间复杂度, 但是还是会 TLE.

变化一下这个 DP 方程:

\[f[i][j] = max\{f[i - w - 1][k] - a_{pk} + a_{pj}\}\]

一般可以用单调队列优化的 DP 都能满足形如 \(f[x]=max(min){f[k]}+g[x]\) 的形式, 那么 我们可以把这里的 \(f[i-w-1][k]\) 看作是上面的 \(f[k]\),\(AP_j\) 看作是上面的 \(g[x]\), 于是就可以从小到大枚举 \(j\), 并用单调队列维护二元组 \((k,f[i-w-1][k])\), 并保证队首的 \(f[i-w-1][k]\) 是最大的, DP 到某个 \(j\) 时, 先把队首所有不合法的 \(f[i-w-1][k]\) 全部弹出, 然后用第一个合法的队首去更新 \(f[i][j]\), 然后将这时的 \(f[i-w-1][j]\) 放入队尾, 并同时维护队列单调性.

而卖出的做法也非常相似, 在这里就不再赘述了

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

#define maximize(__x,__y) __x=max(__x,__y)
#define rep(_var,_begin,_end) for(int _var=_begin;_var<=_end;_var++)
using namespace std;
typedef long long lli;
const int maxn = 2100;
const lli infinit = 0x007f7f7f7f7f7f7fll;

int n, maxP, w;
lli dp[maxn][maxn];
pair<int, lli> que[maxn];

int main(int argc, char** argv)
{
    lli res = -infinit;
    rep(i, 0, maxn - 1) rep(j, 0, maxn - 1)
        dp[i][j] = -infinit;
    scanf("%d%d%d", &n, &maxP, &w);
    // Process dynamic programming while reading data
    for (int i = 1; i <= n; i++) {
        int ap, bp, as, bs;
        scanf("%d%d%d%d", &ap, &bp, &as, &bs);
        // Only selling shares at this day.
        for (int j = 0; j <= as; j++)
            dp[i][j] = - ap * j;
        // Selling / purchasing nothing on this day (copying data)
        for (int j = 0; j <= maxP; j++)
            maximize(dp[i][j], dp[i - 1][j]);
        // The last operation that allows this operation
        int k = i - w - 1;
        if (k >= 0) {
            // Dual-directional queue / deque
            int front = 0, end = 0;
            // Purchasing shares.
            for (int j = 0; j <= maxP; j++) {
                while (front < end && que[front].first < j - as)
                    front += 1;
                while (front < end && que[end - 1].second <= dp[k][j] + ap * j)
                    end -= 1;
                // Enqueue and update data
                que[end++] = make_pair(j, dp[k][j] + ap * j);
                if (front < end)
                    maximize(dp[i][j], que[front].second - ap * j);
            }
            front = 0, end = 0;
            // Selling shares.
            for (int j = maxP; j >= 0; j--) {
                while (front < end && que[front].first > j + bs)
                    front += 1;
                while (front < end && que[end - 1].second <= dp[k][j] + bp * j)
                    end -= 1;
                que[end++] = make_pair(j, dp[k][j] + bp * j);
                if (front < end)
                    maximize(dp[i][j], que[front].second - bp * j);
            }
        }
        // Update final value
        maximize(res, dp[i][0]);
    }
    printf("%lld\n", res);
    return 0;
}