【SCOI2010】股票交易

落日映苍穹つ 2023-06-05 08:55 30阅读 0赞

# Description #

[【SCOI2010】股票交易][SCOI2010]

在T天时间内，第\\(i\\)天股票购入价为\\(ap\_i\\)，出售价为\\(bp\_i\\)，每天最多购入\\(as\_i\\)股，最多出售\\(bs\_i\\)股

任意时刻手中的股票数不能超过\\(Maxp\\)，且两次交易至少间隔\\(W\\)天

最大化收益，初始资金视为无限大

# Solution #

单调队列+dp

根据题意不难设计状态，定义\\(f\[i\]\[j\]\\)表示前\\(i\\)天，手里最后有\\(j\\)个股票的最大收益，那么状态转移方程就是：  
\\\[ f\[i\]\[j\]= \\begin\{cases\} f\[i-1\]\[j\] \\\\ f\[i-w-1\]\[k\]-ap\[i\]\*(j-k) & k\\in\[j-as\[i\],j)\\\\ f\[i-w-1\]\[k\]+bp\[i\]\*(k-j) & k\\in(j,j+bs\[i\]\] \\end\{cases\} \\\]  
以第二个式子为例，我们可以变形得到\\(f\[i\]\[j\]=f\[i-w-1\]\[k\]+ap\[i\]\*k-ap\[i\]\*j\\)

这个式子符合单调队列的一般形式，所以我们可以用单调队列进行优化

第三个式子同理

时间复杂度为\\(O(TMaxp)\\)

# Code #

#include <bits/stdc++.h>
    // check if it is judged online
    namespace shl {
        typedef long long ll;
        inline int read() {
            int ret = 0, op = 1;
            char c = getchar();
            while (!isdigit(c)) {
                if (c == '-') op = -1;
                c = getchar();
            }
            while (isdigit(c)) {
                ret = ret * 10 + c - '0';
                c = getchar();
            }
            return ret * op;
        }
        const int N = 2010;
        int n, m, w;
        int as[N], bs[N], ap[N], bp[N];
        int head, tail, que[N];
        int f[N][N];
        inline int calca(int i, int ww, int k) {
            return f[i - ww - 1][k] + ap[i] * k;
        }
        inline int calcb(int i, int ww, int k) {
            return f[i - ww - 1][k] + bp[i] * k;
        }
        using std::max;
        int main() {
            n = read(), m = read(), w = read();
            for (register int i = 1; i <= n; ++i) {
                ap[i] = read(), bp[i] = read(), as[i] = read(), bs[i] = read();
            } 
            memset(f, -0x7f, sizeof(f));
            for (register int i = 0; i <= n; ++i)  f[i][0] = 0;
            for (register int i = 1; i <= n; ++i) {
                for (register int j = 0; j <= as[i]; ++j) f[i][j] = -ap[i] * j;
                for (register int j = m; j >= 0; --j) f[i][j] = max(f[i][j], f[i - 1][j]);
                if (i - w - 1 < 0) continue ;
                head = 1, tail = 0;
                for (register int j = 0; j <= m; ++j) {
                    while (head <= tail && que[head] < j - as[i]) head++;
                    while (head <= tail && calca(i, w, j) >= calca(i, w, que[tail])) tail--;
                    que[++tail] = j;
                    if (head <= tail) f[i][j] = max(f[i][j], calca(i, w, que[head]) - j * ap[i]);
                }
                head = 1, tail = 0;
                for (register int j = m; j >= 0; --j) {
                    while (head <= tail && que[head] > j + bs[i]) head++;
                    while (head <= tail && calcb(i, w, j) >= calcb(i, w, que[tail])) tail--;
                    que[++tail] = j;
                    if (head <= tail) f[i][j] = max(f[i][j], calcb(i, w, que[head]) - j * bp[i]);
                }           
            }   
            int ans = 0;    
            for (register int i = 0; i <= m; ++i) ans = max(ans, f[n][i]);
            printf("%d\n", ans);
            return 0;
        }
    }
    int main() {
    #ifdef LOCAL
        freopen("textname.in", "r", stdin);
        freopen("textname.out", "w", stdout);
    #endif
        shl::main();
        return 0;
    }

转载于:https://www.cnblogs.com/shl-blog/p/11618263.html

[SCOI2010]: https://www.luogu.org/problem/P2569