「Bzoj 1854」「SCOI2010」股票交易 (单调队列优化DP)

BZOJ 1854
题意：第 $i$ 天的股票买入价为每股 $AP_i$，第 $i$ 天的股票卖出价为每股 $BP_i$, 股票交易所规定在两次交易（某一天的买入或者卖出均算是一次交易）之间，至少要间隔 $W$ 天, 在任何时间，一个人的手里的股票数不能超过 \text{MaxP}。在第 $1$ 天之前，有无限钱，但是没有任何股票，求 $T$ 天以后最大收益。

容易设$dp(i,j)$为前$i$天有$j$股票的最大收益
则分情况讨论
1、买入股票
$$
dp(i,j)=\max_{k \in [j-AS[i], j-1]}(dp(i,j), dp(i-w-1,k) + AP_i (k-j))
$$
2、卖出股票
$$
dp(i,j)=\max_{k \in [j+1,j+BS[i]]}(dp(i,j), dp(i-w-1,k) + BP_i (j-k))
$$
3、什么也不做
$$
dp(i,j)=\max(dp(i,j), dp(i-1,j))
$$

初值：
$$
dp(i,j)=-AP_i \cdot j
$$
其中$0 \leq j \leq AS_i$
其余均为$-∞$

然后考虑优化
我们将$i,j$看作定值，则将与$k$无关式子移到$\max$外面，发现这可以单调队列优化。

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<set>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db long double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const int MAXN = 2000 + 5, INF = 2000000000;

    int n, maxP, w, AP[MAXN], BP[MAXN], AS[MAXN], BS[MAXN];
    int dp[MAXN][MAXN];
    int l, r, q[MAXN];

    void clean() {
    }
    int solve() {

        clean();

        cin >> n >> maxP >> w;
        for (int i = 1; i <= n; ++i) {
            scanf("%d%d%d%d", &AP[i], &BP[i], &AS[i], &BS[i]);
        }

        for (int i = 0; i <= n; ++i)
        for (int j = 0; j <= maxP; ++j) dp[i][j] = -INF;

        for (int i = 1; i <= n; ++i) 
        for (int j = 0; j <= AS[i]; ++j) dp[i][j] = -AP[i] * j;

        for (int i = 1; i <= n; ++i) {
            l = 1, r = 0;
            for (int j = 0; j <= maxP; ++j) dp[i][j] = max(dp[i][j], dp[i - 1][j]);
            if (i <= w) continue ;
            for (int j = 0; j <= maxP; ++j) { // buy
                while (l <= r && q[l] < j - AS[i]) ++l;
                while (l <= r && dp[i - w - 1][j] + AP[i] * j >= dp[i - w - 1][q[r]] + AP[i] * q[r]) --r;
                q[++r] = j;
                if (l <= r) dp[i][j] = max(dp[i - w - 1][q[l]] + AP[i] * q[l] - AP[i] * j, dp[i][j]);
            }
            l = 1, r = 0;
            for (int j = maxP; j >= 0; --j) { // sell
                while (l <= r && q[l] > j + BS[i]) ++l;
                while (l <= r && dp[i - w - 1][j] + BP[i] * j >= dp[i - w - 1][q[r]] + BP[i] * q[r]) --r;
                q[++r] = j;
                if (l <= r) dp[i][j] = max(dp[i - w - 1][q[l]] + BP[i] * q[l] - BP[i] * j, dp[i][j]);
            }
        }

        //for (int i = 0; i <= n; ++i)
        //for (int j = 0; j <= maxP; ++j) printf("i=%d, j=%d, dp=%d\n", i, j, dp[i][j]);

        int ans = 0;
        for (int j = 0; j <= maxP; ++j) ans = max(ans, dp[n][j]);

        cout << ans;

        return 0;
    }
}
int main() { 
    flyinthesky::solve();
    return 0;
}
/*
*/