Menu
Article ACM

POJ 1742 Coins

NodeKey

NodeKey

• 2 min read

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;
}
Share