Menu
Article ACM

HDU 3401 Trade

NodeKey

NodeKey

• 3 min read

第一次听说用单调队列来优化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;
}
Share