第一次听说用单调队列来优化DP……
只能说见得少了……

单调队列的限制很多,我已经几百年没用它了……
但是有一些dp问题的子问题,的确可以转化成典型的单调队列问题,用单调队列优化之,可以将复杂度下降一个数量级。

题意:
有个人看穿了股市所有行情,现在他的本金无限,问可以赚多少钱。
这里的股市限制炒鸡多。
有限制:

  1. 最大所持股票数量
  2. 每天最大购买量
  3. 每条最大卖出量
  4. 当天购买的股票必须至少 n 天后才能卖出

最后给你看穿天数,每天收购与卖出价格。

思路:

可以说是单调队列优化DP的入门题了……
设 dp [ i ][ j ] 为第 i 天持有 j 股的收益。
则状态转移的规则就是 取

  1. 不买不卖 dp [ i - 1][ j ]
  2. 买入 限制下的 股数 的最收益 dp[ i - w + 1][ k ] - (j-k) * in[i]
  3. 卖出 限制下的 股数 的最收益 dp[ i - w + 1][ k ] + (k-j) * out[i]

上 3 者的最大值。

仔细考虑一下,就买而说,通过方程移项,得
dp[i][j]+j \times in[i] = \max \left( dp[r][k]+k \times pa[i] \right)

右边的式子,是一个在固定长度的区间的最值问题,可用单调队列求解之。

AC Code

#include <bits/stdc++.h>

using namespace std;

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary));

const int maxn = 2005;
const int inf = 0x3f3f3f3f;

int n, num_limit, limit;
int in[maxn], out[maxn], in_limit[maxn], out_limit[maxn];
int dp[maxn][maxn];
struct node {
    int x;
    int p;
} q[2005], temp;
int front, rear;
int main()
{
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d%d", &n, &num_limit, &limit);
        range(i, 1, n) scanf("%d %d %d %d", in + i, out + i, in_limit + i, out_limit + i);
        fill(dp, -0x3f);
        range(i, 1, limit + 1) each(j, in_limit[i] + 1) dp[i][j] = (-in[i] * j);
        range(i, 2, n)
        {
            each(j, num_limit + 1) dp[i][j] = max(dp[i][j], dp[i - 1][j]);
            if (i <= limit + 1)
                continue;
            front = rear = 1;
            each(j, num_limit + 1)
            {
                temp.p = j;
                temp.x = dp[i - limit - 1][j] + in[i] * j;
                while (front < rear && q[rear - 1].x < temp.x)
                    rear--;
                q[rear++] = temp;
                while (front < rear && q[front].p + in_limit[i] < j)
                    front++;
                dp[i][j] = max(dp[i][j], q[front].x - in[i] * j);
            }
            front = rear = 1;
            reach(j, num_limit + 1)
            {
                temp.p = j;
                temp.x = dp[i - limit - 1][j] + out[i] * j;
                while (front < rear && q[rear - 1].x < temp.x)
                    rear--;
                q[rear++] = temp;
                while (front < rear && q[front].p - out_limit[i] > j)
                    front++;
                dp[i][j] = max(dp[i][j], q[front].x - out[i] * j);
            }
        }
        int ans = 0;
        each(i, num_limit + 1) ans = max(ans, dp[n][i]);
        printf("%d\n", ans);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注