单调队列优化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;
}
最小割

ZOJ 3475 The Great Wall I

Posted on

最小割建图好题!!

昨天比赛的最小割,当时没看出来,实际上需要建图转化一下,这道题非常显然!!!
比赛后不想看题解,问了一下Yasola,指点了一下马上懂了!!

题意:
有n×m的地图,地图上最多有6个国家,现在K国要修长城,来防御敌对国家,6个国家中除了K国和一个敌对国家,其余国家都是友好国家,想要进供从而使得自己在长城防御范围内。建立长城的每一个花费都已经给出。
问最小花费。

思路:
将地图以外的地方视为敌对,将一个地图上的格子与其上下左右相连。
对于一个长城,实际上就是将K过与友好国家 与 敌对国家割开的最小割。
又因为点数和边数都很少,最多通过枚举 2^5 枚举将友好国家包围的情况,每次求一下最小割即可。

AC Code

#include <bits/stdc++.h>

using namespace std;
const int maxn = 404;
const int maxm = 1e4 + 5;
const int inf = 0x3f3f3f3f;

int n, m, st, en, idx, tidx;
int cur[maxn], level[maxn], head[maxn], thead[maxn];
int cap[maxm];
int afford[10], x[10], y[10];

struct node {
    int to, next;
    int cap;
    node() {}
    node(int _to, int _next, int _cap) { to = _to, next = _next, cap = _cap; }
} edges[maxm << 1];

queue<int> que;

int getNode(int a, int b) { return a * m + b; }

void addEdge(int u, int v, int c)
{
    edges[idx] = node(v, head[u], c);
    head[u] = idx++;
    edges[idx] = node(u, head[v], c);
    head[v] = idx++;
}

bool bfs()
{
    memset(level, -1, sizeof level);
    que.push(st);
    level[st] = 0;
    int u;
    while (!que.empty()) {
        u = que.front();
        que.pop();
        for (int id = head[u]; ~id; id = edges[id].next) {
            int v = edges[id].to;
            if (edges[id].cap > 0 && level[v] == -1) {
                level[v] = level[u] + 1;
                que.push(v);
            }
        }
    }
    return level[en] != -1;
}

int dfs(int u, int low)
{
    int cflow;
    if (u == en)
        return low;
    for (int& id = cur[u]; ~id; id = edges[id].next) {
        int v = edges[id].to;
        if (edges[id].cap > 0 && level[v] == level[u] + 1
            && (cflow = dfs(v, min(low, edges[id].cap)))) {
            edges[id].cap -= cflow;
            edges[id ^ 1].cap += cflow;
            return cflow;
        }
    }
    return 0;
}

int dinic()
{
    int ans = 0, cflow;
    while (bfs()) {
        for (int i = 0; i <= en; i++)
            cur[i] = head[i];
        while ((cflow = dfs(st, inf)))
            ans += cflow;
    }
    return ans;
}

int main()
{
    int c;
    while (scanf("%d %d", &n, &m) != EOF) {
        memset(head, -1, sizeof head), idx = 0;
        st = n * m, en = n * m + 1;
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j < m; j++) {
                scanf("%d", &c);
                addEdge(i == 0 ? en : getNode(i - 1, j), i == n ? en : getNode(i, j), c);
            }
            if (i == n)
                continue;
            for (int j = 0; j <= m; j++) {
                scanf("%d", &c);
                addEdge(j == 0 ? en : getNode(i, j - 1), j == m ? en : getNode(i, j), c);
            }
        }
        scanf("%d", &c);
        for (int i = 0; i < c; i++) {
            scanf("%d %d %d", afford + i, x + i, y + i);
            if (afford[i] == 0)
                swap(afford[0], afford[i]), swap(x[0], x[i]), swap(y[0], y[i]);
            else if (afford[i] < 0)
                addEdge(getNode(x[i], y[i]), en, inf), c--, i--;
        }
        memcpy(thead, head, sizeof head), tidx = idx;
        for (int i = 0; i < idx; i++)
            cap[i] = edges[i].cap;
        int ans = inf;
        for (int i = 1; i < (1 << c); i += 2) {
            int cost = 0;
            memcpy(head, thead, sizeof thead), idx = tidx;
            for (int i = 0; i < idx; i++)
                edges[i].cap = cap[i];
            for (int j = 0; j < c; j++) {
                if (i & (1 << j)) {
                    cost -= afford[j];
                    addEdge(st, getNode(x[j], y[j]), inf);
                }
            }
            cost += dinic();
            ans = min(ans, cost);
        }
        printf("%d\n", ans);
    }
    return 0;
}