单调队列优化DP

POJ 1742 Coins

Posted on

OK,被逼得去学单调队列优化的dp

单调队列可以优化的DP有一大类就是多重背包。

因为本人是个DP弱菜,建议还是看其他人的博文……
推荐博文 点这里

Coins 是 楼教主的男人八题中可以说是最简单的一道了。

简单说就是可行性多重背包,背包九讲中有关于可行性多重背包 \( O \left( VN \right) \)算法的说明,虽然点到了单调队列优化,但也只是一笔带过。

题意:
有很多个硬币,各有价值a[i]与数量c[i],问你能构成的价值种数有多少。

思路:
这里简单说一下我对单调队列优化的理解吧

其实这里根本算不上单调队列,只能说是队列,其实就是问题被简化了。
对于每一个价值,都可以被转化成 \( d + n \times a[i] \) , 其中 \( d \in \left[ 0 , a[i] \right) \)
简单说就同余关系啦
那么对于一个价值 k ,若 \( k - n \times a[i] \) ,其中 \( n \in \left[ 1, c[i] ] \) 是可以被构造的,那么k就可以被构造。

AC Code

#include <cstdio>
#include <algorithm>
#include <cstring>

#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));

using namespace std;

const int maxn = 105;
const int maxm = 1e5 + 5;
const int inf = 0x3f3f3f3f;

int n, m;
int a[maxn], c[maxn];
bool dp[maxm], deq[maxm];

int main()
{
    while (scanf("%d %d", &n, &m) != EOF && n + m > 0) {
        each(i, n) scanf("%d", a + i);
        each(i, n) scanf("%d", c + i);
        fill(dp, dp + m + 1, false), dp[0] = true;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (c[i] == 1) {
                for (int v = m; v >= a[i]; v--)
                    if (!dp[v] && dp[v - a[i]])
                        dp[v] = true, ans++;
                continue;
            }
            if (a[i] * c[i] >= m) {
                for (int v = a[i]; v <= m; v++)
                    if (dp[v - a[i]] && !dp[v])
                        dp[v] = true, ans++;
                continue;
            }
            for (int rem = 0; rem < a[i]; rem++) {
                int s = 0, e = -1, sum = 0;
                for (int v = rem; v <= m; v += a[i]) {
                    if (s + c[i] == e)
                        sum -= deq[s++];
                    deq[++e] = dp[v];
                    sum += dp[v];
                    if (!dp[v] && sum)
                        dp[v] = true, ans++;
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}
单调队列优化DP

HDU 3401 Trade

Posted on

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