(luogu2569) 股票交易

发表于 分类于 ，

原题链接

思路:

背包 + 单调队列优化 dp

设 \(d_{i,j}\) 为第 \(i\) 天持有 \(j\) 股股票的最大利润.

一共有四种转移途径:

  • 1 不进行交易，转移方程为:

\[ d_{i,j} = d_{i-1,j} \]

  • 2 首次买入，对 \(j \le AS_i\), 有:

\[ d_{i,j} = -j \times AP_i \]

  • 3 再次买入，对 \(i > W + 1\), 有:

\[ d_{i,j} = \max_k \{d_{i-W-1,k} - (j-k)AP_i\}\\ k \in [j-AS_i, j) \cap [1,MaxP] \]

  • 4 卖出，对 \(i > W + 1\), 有:

\[ d_{i,j} = \max_k \{d_{i-W-1,k} + (k-j)BP_i\}\\ k \in (j, j+BS_i] \cap [1,MaxP] \]

转移 1, 2 可以直接判定。对于转移 3, 4 可以发现 \(k\) 的左右端点随 \(j\) 的增加单调不降， 所以可以使用单调队列优化.

对于 3 的转移方程，移项可得:

\[ d_{i,j} = \max_k \{d_{i-W-1,k} + kAP_i\} - jAP_i \]

同样地，对于 4 的转移方程移项得:

\[ d_{i,j} = \max_k \{d_{i-W-1,k} + kBP_i\} - jBP_i \]

所以使用单调队列维护的是 \(d_{i-W-1,k} + kAP_i\) 和 \(d_{i-W-1,k} + kBP_i\)

代码:

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <cstdio>
#include <cctype>
#include <cstring>
#include <deque>
#include <algorithm>
using namespace std;
using LL = long long;
const int Mn(2050), Mm(2050);
template<typename T> void qrd(T& x) {   //快读
    x = 0;
    int c = getchar();
    while(!isdigit(c)) {
        c = getchar();
    }
    while(isdigit(c)) {
        x = x*10 + c - '0';
        c = getchar();
    }
}
template<typename T, typename... Ts> void qrd(T& x, Ts&... xs) {
    qrd(x); qrd(xs...);
}

struct Qd { //队列元素
    LL x, p;
    bool operator < (const Qd& rhs) const {
        return x < rhs.x;
    }
};
struct Gq { //单调队列
    deque<Qd> q;
    const Qd& front() {
        return q.front();
    }
    void pop() {
        q.pop_front();
    }
    void clear() {
        q.clear();
    }
    void push(Qd x) {
        while(!q.empty() && q.back()<x) {
            q.pop_back();
        }
        q.push_back(x);
    }
}qb, qs;    //queue_buy queue_sell

LL d[Mn][Mm];   //dp数组

int main() {
    int n,m,w;
    qrd(n,m,w);
    memset(d[0],0xc0,sizeof d[0]);  //初始化为极小值
    d[0][0] = 0;
    for(int i(1);i<=n;++i) {
        LL ap,bp,as,bs;
        qrd(ap,bp,as,bs);
        for(int j(0);j<=m;++j) {
            d[i][j] = d[i-1][j];    //转移1
            if(j<=as) {
                d[i][j] = max(d[i][j],-ap*j);   //转移2
            }
        }
        if(i>w+1) {
            qb.clear();
            qb.push({d[i-w-1][0],0});
            for(int j(1);j<=m;++j) {
                if(qb.front().p<j-as) {
                    qb.pop();
                }
                d[i][j] = max(d[i][j],qb.front().x-j*ap);   //转移3
                qb.push({d[i-w-1][j]+j*ap,j});
            }
            qs.clear();
            qs.push({d[i-w-1][m],m});
            for(int j(m);j>=0;--j) {
                if(qs.front().p>j+bs) {
                    qs.pop();
                }
                d[i][j] = max(d[i][j],qs.front().x-j*bp);   //转移4
                qs.push({d[i-w-1][j]+j*bp,j});
            }
        }
    }
    printf("%lld",d[n][0]);
    return 0;
}