Skip to content

LibreOJ - 10183. 股票交易

检测到 KaTeX 加载失败,可能会导致文中的数学公式无法正常渲染。

题面

题目描述

最近 lxhgww 又迷上了投资股票,通过一段时间的观察和学习,他总结出了股票行情的一些规律。

通过一段时间的观察,lxhgww 预测到了未来 TT 天内某只股票的走势,第 ii 天的股票买入价为每股 APi\mathit{AP}_i,第 ii 天的股票卖出价为每股 BPiBP_i(数据保证对于每个 ii,都有 APiBPi\mathit{AP}_i \geq \mathit{BP}_i),但是每天不能无限制地交易,于是股票交易所规定第 ii 天的一次买入至多只能购买 ASi\mathit{AS}_i 股,一次卖出至多只能卖出 BSi\mathit{BS}_i 股。

另外,股票交易所还制定了两个规定。为了避免大家疯狂交易,股票交易所规定在两次交易(某一天的买入或者卖出均算是一次交易)之间,至少要间隔 WW 天,也就是说如果在第 ii 天发生了交易,那么从第 i+1i + 1 天到第 i+Wi + W 天,均不能发生交易。同时,为了避免垄断,股票交易所还规定在任何时间,一个人的手里的股票数不能超过 MaxP\mathit{MaxP}

在第 11 天之前,lxhgww 手里有一大笔钱(可以认为钱的数目无限),但是没有任何股票,当然,TT 天以后,lxhgww 想要赚到最多的钱,聪明的程序员们,你们能帮助他吗?

输入格式

输入数据第一行包括 33 个整数,分别是 TTMaxP\mathit{MaxP}WW

接下来 TT 行,第 ii 行代表第 i1i-1 天的股票走势,每行 44 个整数,分别表示 APi,BPi,ASi,BSi\mathit{AP}_i, \mathit{BP}_i, \mathit{AS}_i, \mathit{BS}_i

输出格式

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

输入输出样例

样例输入 #1

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

样例输出 #1

3

提示

  • 对于 30%30\% 的数据,0W<T500 \leq W < T \leq 501MaxP501 \leq \mathit{MaxP}\leq 50
  • 对于 50%50\% 的数据,0W<T20000 \leq W < T \leq 20001MaxP501 \leq \mathit{MaxP} \leq 50
  • 对于 100%100\% 的数据,0W<T20000 \leq W < T \leq 20001MaxP20001 \leq \mathit{MaxP} \leq 20001BPiAPi10001 \leq \mathit{BP}_i \leq \mathit{AP}_i \leq 10001ASi,BSiMaxP1 \leq \mathit{AS}_i, \mathit{BS}_i \leq \mathit{MaxP}

思路

先考虑朴素做法。

对于每一天,有 44 种情况:

  1. 不操作。

    此时收益与上一天持平。

    转移方程:fi,j=fi1,jf_{i, j} = f_{i - 1, j}

  2. 从头开始买入股票。此状态即为初始状态。

    此时收益要扣除买股票的钱,当买 kk 张股票时,收益为 k×APi-k \times \mathit{AP}_i

    转移方程:fi,j=j×APif_{i, j} = -j \times \mathit{AP}_i

  3. 在前一天的基础上买入股票。

    由于前 1iW21 \sim i - W - 2 天的最优收益已经转移到了 iW1i - W - 1 天上,所以只需要枚举第 ii 天买多少张股票,并在第 iW1i - W - 1 天中对应股票数量的收益的基础上扣除相应金额即可。

    转移方程:fi,j=maxk=jASij1{fiw1,k(jk)×APi}f_{i, j} = \max_{k = j - \mathit{AS}_i}^{j - 1}\{f_{i - w - 1, k} - (j - k) \times \mathit{AP}_i\}

  4. 在前一天的基础上卖出股票。

    枚举第 ii 天卖多少张股票,并在第 iW1i - W - 1 天中对应股票数量的收益的基础上增加相应金额即可。

    转移方程:fi,j=maxk=j+1j+BSi{fiw1,k+(kj)×BPi}f_{i, j} = \max_{k = j + 1}^{j + \mathit{BS}_i}\{f_{i - w - 1, k} + (k - j) \times \mathit{BP}_i\}


不难发现,3344 两个操作是可以被优化的。

33 中的方程可以被转化为:

fi,j=maxk=jASij1{fiw1,k(jk)×APi}=maxk=jASij1{fiw1,kj×APi+k×APi}=maxk=jASij1{fiw1,k+k×APi}j×APi\begin{aligned} f_{i, j} &= \max_{k = j - \mathit{AS}_i}^{j - 1}\{f_{i - w - 1, k} - (j - k) \times \mathit{AP}_i\} \\ &= \max_{k = j - \mathit{AS}_i}^{j - 1}\{f_{i - w - 1, k} - j \times \mathit{AP}_i + k \times \mathit{AP}_i\} \\ &= \max_{k = j - \mathit{AS}_i}^{j - 1}\{f_{i - w - 1, k} + k \times \mathit{AP}_i\} - j \times \mathit{AP}_i \\ \end{aligned}

同理,44 中的方程可以被转化为:

fi,j=maxk=j+1j+BSi{fiw1,k+(kj)×BPi}=maxk=j+1j+BSi{fiw1,k+k×BPij×BPi}=maxk=j+1j+BSi{fiw1,k+k×BPi}j×BPi\begin{aligned} f_{i, j} &= \max_{k = j + 1}^{j + \mathit{BS}_i}\{f_{i - w - 1, k} + (k - j) \times \mathit{BP}_i\} \\ &= \max_{k = j + 1}^{j + \mathit{BS}_i}\{f_{i - w - 1, k} + k \times \mathit{BP}_i - j \times \mathit{BP}_i\} \\ &= \max_{k = j + 1}^{j + \mathit{BS}_i}\{f_{i - w - 1, k} + k \times \mathit{BP}_i\} - j \times \mathit{BP}_i \\ \end{aligned}

使用单调队列维护即可。

代码

#include <iostream>
#include <cstring>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 2005;

int n, m, w, f[N][N];

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);

    memset(f, 0xcf, sizeof(f));

    cin >> n >> m >> w;

    for (int i = 1; i <= n; i++) {
        f[i][0] = 0;

        int ap, bp, as, bs;

        cin >> ap >> bp >> as >> bs;

        // [2]: 从 0 张开始买入
        for (int j = 0; j <= as; j++) {
            f[i][j] = -j * ap;
        }

        // [1]: 不操作
        for (int j = 0; j <= m; j++) {
            f[i][j] = std::max(f[i][j], f[i - 1][j]);
        }

        if (i - w - 1 > 0) {
            // [3]: 买入
            for (int j = 0; j <= m; j++) {
                for (int k = std::max(j - as, 0); k < j; k++) {
                    f[i][j] = std::max(f[i][j], f[i - w - 1][k] - (j - k) * ap);
                }
            }

            // [4]: 卖出
            for (int j = 0; j <= m; j++) {
                for (int k = j + 1; k <= std::min(j + bs, m); k++) {
                    f[i][j] = std::max(f[i][j], f[i - w - 1][k] + (k - j) * bp);
                }
            }
        }
    }

    cout << f[n][0] << endl;

    return 0;
}
#include <iostream>
#include <cstring>
#include <deque>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 2005;

int n, m, w, f[N][N];

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);

    memset(f, 0xcf, sizeof(f));

    cin >> n >> m >> w;

    for (int i = 1; i <= n; i++) {
        f[i][0] = 0;

        int ap, bp, as, bs;

        cin >> ap >> bp >> as >> bs;

        // [2]: 从 0 张开始买入
        for (int j = 0; j <= as; j++) {
            f[i][j] = -j * ap;
        }

        // [1]: 不操作
        for (int j = 0; j <= m; j++) {
            f[i][j] = std::max(f[i][j], f[i - 1][j]);
        }

        if (i - w - 1 > 0) {
            // [3]: 买入
            std::deque<int> q1;
            for (int j = 0; j <= m; j++) {
                while (!q1.empty() && q1.front() < j - as) q1.pop_front();
                while (!q1.empty() && f[i - w - 1][q1.back()] + q1.back() * ap <= f[i - w - 1][j] + j * ap) q1.pop_back();
                q1.push_back(j);
                f[i][j] = std::max(f[i][j], f[i - w - 1][q1.front()] - (j - q1.front()) * ap);
            }

            // [4]: 卖出
            std::deque<int> q2;
            for (int j = m; ~j; j--) {
                while (!q2.empty() && q2.front() > j + bs) q2.pop_front();
                while (!q2.empty() && f[i - w - 1][q2.back()] + q2.back() * bp <= f[i - w - 1][j] + j * bp) q2.pop_back();
                q2.push_back(j);
                f[i][j] = std::max(f[i][j], f[i - w - 1][q2.front()] + (q2.front() - j) * bp);
            }
        }
    }

    cout << f[n][0] << endl;

    return 0;
}