Skip to content

「SCOI2010」股票交易

检测到 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}

使用单调队列维护即可。

#代码

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
#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;
}
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 <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;
}