P2569 [SCOI2010]股票交易 P2569 [SCOI2010]股票交易

数据结构优化DP。

用(f[i][j])表示第(i)天手里还有(j)张股票的最大收益。

分四种情况转移：

直接买入，不承接之前的：

f[i][j] = -ap * j;

不卖也不买：

f[i][j] = std::max(f[i][j], f[i - 1][j]);

卖出股票：

f[i][j] = std::max(f[i][j], f[i - w - 1][k] + (k - j) * bp);

买入股票，承接之前的：

f[i][j] = std::max(f[i][j], f[i - w - 1][k] - (j - k) * ap);

为啥只能从(i - w - 1)转移过来呢？因为(i - w - 1)可能是从更前面转移过来的，比如说(i - w - 2)，这样(i)其实也是从(i - w - 2)转移过来的。

可以发现，第三种和第四种情况可以把(j)提出来：

f[i][j] = max(f[i][j], std::max(f[i - w - 1][k] + k * bp) - j * bp);
f[i][j] = max(f[i][j], std::max(f[i - w - 1][k] + k * ap) - j * ap);

这样我们就可以用单调队列优化了，可以把(f[i - w - 1][k] + k * bp/ap)放入单调队列里，每次(O(1))找到最大值，总复杂度(O(n^2))。

#include <bits/stdc++.h>

inline long long read() {
    long long s = 0, f = 1; char ch;
    while(!isdigit(ch = getchar())) (ch == '-') && (f = -f);
    for(s = ch ^ 48;isdigit(ch = getchar()); s = (s << 1) + (s << 3) + (ch ^ 48));
    return s * f;
}

const int N = 2005;
int T, P, w, l, r, ap, bp, as, bs, ans;
int p[N], f[N][N];

int main() {

    T = read(); P = read(); w = read();
    
    memset(f, -0x3f, sizeof(f));

    for(int i = 1;i <= T; i++) {

        ap = read(), bp = read(), as = read(), bs = read();

        for(int j = 0;j <= as; j++) f[i][j] = -ap * j;

        for(int j = 0;j <= P; j++) f[i][j] = std::max(f[i][j], f[i - 1][j]);
        
        if(i <= w) continue;

        l = 1, r = 0;
        for(int j = P;j >= 0; j--) {
            while(l <= r && p[l] > j + bs) l++;
            // std::cout << l << std::endl;
            while(l <= r && f[i - w - 1][p[r]] + p[r] * bp <= f[i - w - 1][j] + j * bp) r--;
            p[++r] = j;
            if(l <= r) f[i][j] = std::max(f[i][j], f[i - w - 1][p[l]] + p[l] * bp - j * bp);
        }

        l = 1, r = 0;
        for(int j = 0;j <= P; j++) {
            while(l <= r && p[l] < j - as) l++;
            while(l <= r && f[i - w - 1][p[r]] + p[r] * ap <= f[i - w - 1][j] + j * ap) r--;
            p[++r] = j;
            if(l <= r) f[i][j] = std::max(f[i][j], f[i - w - 1][p[l]] + p[l] * ap - j * ap);
        }
    }

    for(int i = 0;i <= P; i++) ans = std::max(ans, f[T][i]);

    printf("%d", ans);
    
    return 0;
}

P2569 [SCOI2010]股票交易 P2569 [SCOI2010]股票交易

相关推荐