P1450:[HAOI2008]硬币购物题解

主要思路

我们先来考虑无限制的版本,也就是不考虑询问的硬币数量限制。我们可以用一个完全背包搞一搞,复杂度为线性。

dp[0] = 1;
for (int i = 0; i < 4; i++)
    for (int j = ci[i]; j < MAX_N; j++)
        dp[j] += dp[j - ci[i]];

那么我们如何做到复杂度小的询问呢?我们可以考虑容斥原理,把答案搞成:

\[ dp[s] – dp[s-(d_{1}+1)*c_{1}] – dp[s-(d_{2}+1)*c_{2}] – dp[s-(d_{3}+1)*c_{3}] – dp[s-(d_{4}+1)*c_{4}] + dp[s-(d_{1}+1)*c_{1}-(d_{2}+1)*c_{2}] + dp[s-(d_{1}+1)*c_{1}-(d_{3}+1)*c_{3}] + dp[s-(d_{1}+1)*c_{1}-(d_{4}+1)*c_{4}] \dots \]

然后用二进制搞个容斥就行了:

// P1450.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX_N = 101000;
int ci[5], tot, di[5], si;
ll dp[101000];
int main()
{
    for (int i = 0; i < 4; i++)
        scanf("%d", &ci[i]);
    dp[0] = 1;
    for (int i = 0; i < 4; i++)
        for (int j = ci[i]; j < MAX_N; j++)
            dp[j] += dp[j - ci[i]];
    scanf("%d", &tot);
    while (tot--)
    {
        for (int j = 0; j < 4; j++)
            scanf("%d", &di[j]);
        scanf("%d", &si);
        ll ans = 0;
        for (int i = 0; i < 16; i++)
        {
            ll C = si, T = 0;
            for (int j = 0; j < 4; j++)
                if ((i >> j) & 1)
                    C -= (di[j] + 1) * ci[j], T ^= 1;
            if (C < 0)
                continue;
            ans += (T ? -1 : 1) * dp[C];
        }
        printf("%lld\n", ans);
    }
    return 0;
}

 

发布者

Kal0rona

江西师大附中全机房最弱

发表评论

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