一道单调队列优化\(DP\)

BZOJ原题链接

洛谷原题链接

朴素的\(DP\)方程并不难想。

定义\(f[i][j]\)表示到第\(i\)天，手上持有\(j\)股时的最大收益。

转移方程可以分成四个部分。

1. 第\(i\)天为空手时买股票

2. 第\(i\)天不进行交易

3. 第\(i\)天在之前基础上买

4. 第\(i\)天在之前基础上卖

显然决策增减满足单调性，可以用单调队列维护，注意第\(4\)项要倒序才能维护。

#include<cstdio>
#include<cstring>
using namespace std;
const int N = 2010;
int f[N][N], AP[N], BP[N], AS[N], BS[N], q[N];
int re()
{
    int x = 0;
    char c = getchar();
    bool p = 0;
    for (; c<'0' || c>'9'; c = getchar())
        p = (c == '-' || p) ? 1 : 0;
    for (; c >= '0'&&c <= '9'; c = getchar())
        x = x * 10 + (c - '0');
    return p ? -x : x;
}
inline int minn(int x, int y)
{
    return x < y ? x : y;
}
inline int maxn(int x, int y)
{
    return x > y ? x : y;
}
int main()
{
    int i, j, n, m, w, l, r;
    n = re();
    m = re();
    w = re();
    memset(f, 250, sizeof(f));
    for (i = 1; i <= n; i++)
    {
        AP[i] = re();
        BP[i] = re();
        AS[i] = re();
        BS[i] = re();
        f[i][0] = 0;
    }
    for (i = 1; i <= n; i++)
    {
        for (j = 0; j <= AS[i]; j++)
            f[i][j] = -AP[i] * j;
        for (j = m; j >= 0; j--)
            f[i][j] = maxn(f[i][j], f[i - 1][j]);
        if (i - w - 1 > 0)
        {
            for (r = j = 0, l = 1; j <= m; j++)
            {
                while (l <= r && q[l] < j - AS[i])
                    l++;
                while (l <= r && f[i - w - 1][j] + AP[i] * j >= f[i - w - 1][q[r]] + AP[i] * q[r])
                    r--;
                q[++r] = j;
                if (l <= r)
                    f[i][j] = maxn(f[i][j], f[i - w - 1][q[l]] - AP[i] * (j - q[l]));
            }
            for (r = 0, l = 1, j = m; j >= 0; j--)
            {
                while (l <= r && q[l] > j + BS[i])
                    l++;
                while (l <= r && f[i - w - 1][j] + BP[i] * j >= f[i - w - 1][q[r]] + BP[i] * q[r])
                    r--;
                q[++r] = j;
                if (l <= r)
                    f[i][j] = maxn(f[i][j], f[i - w - 1][q[l]] + BP[i] * (q[l] - j));
            }
        }
    }
    printf("%d", f[n][0]);
    return 0;
}