(luogu2569) 股票交易

发表于 | 分类于 ，

原题链接

思路:

背包+单调队列优化dp

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

一共有四种转移途径:

  • 1 不进行交易, 转移方程为:
  • 2 首次买入, 对$j \le AS_i$, 有:
  • 3 再次买入, 对$i > W + 1$, 有:
  • 4 卖出, 对$i > W + 1$, 有:

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

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

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

所以使用单调队列维护的是$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
#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;
}