洛谷P1450/HAOI2008 硬币购物

@Pelom  November 4, 2019

题意

硬币购物一共有$4$种硬币。面值分别为$c_1,c_2,c_3,c_4$
某人去商店买东西,去了$t$次。每次带$d_i$枚$c_i$硬币,买$s$的价值的东西,请问每次有多少种付款方法

数据范围:$d_i,s \le 100000$

题解

显然不能直接多重背包,会TLE
若不考虑限制条件,先当作完全背包处理,再在每次询问的时候将超出部分的情况减去
需要减去的部分也是一个完全背包,容量为$s-c_i*(d_i+1)$
那么合法的情况就为$$f[s]-f[s-c_i*(d_i+1)]$$
推广到多种硬币的情况,需要用到容斥,可用二进制枚举每种硬币的选择情况

代码:

#include<iostream>
#include<cstdio>
using namespace std;
typedef long long LL;
const int S=100000;
int t,s;
int c[5],d[5];
LL dp[S+10];
LL ans;
int main(){
    for(int i=1;i<=4;i++)
        scanf("%d",&c[i]);
    scanf("%d",&t);
    dp[0]=1;
    for(int i=1;i<=4;i++)
        for(int j=c[i];j<=S;j++)
            dp[j]+=dp[j-c[i]];
    for(;t--;){
        ans=0;
        for(int i=1;i<=4;i++)
            scanf("%d",&d[i]);
        scanf("%d",&s);
        for(int i=0;i<(1<<4);i++){
            int t=s;
            bool f=0;
            for(int j=1;j<=4;j++)
                if(i&(1<<(j-1))){
                    t-=c[j]*(d[j]+1);
                    f^=1;
                }
            if(t<0)
                continue;
            if(f)
                ans-=dp[t];
            else ans+=dp[t];
        }
        printf("%lld\n",ans);
    }
    return 0;
}

添加新评论