BZOJ-1042：硬币购物（背包+容斥）

题意：硬币购物一共有4种硬币。面值分别为c1,c2,c3,c4。某人去商店买东西，去了tot次。每次带di枚ci硬币，买si的价值的东西。请问每次有多少种付款方法。

思路：这么老的题，居然今天才做到...背包的复杂度是比较高的。加上tot次询问会爆炸。能不能预处理，然后容斥得到答案呢？
      先求一个完全背包，求出方案数，dp[]。
      然后对于具体的询问，减去不合法的情况。
      对于c[i]，它发贡献是dp[S-c[i]*(d[i]+1)];
      那么会重复减，所以又加回来...

#include<bits/stdc++.h>

#define rep(i,a,b) for(int i=a;i<=b;i++)

#define ll long long

using namespace std;

const int maxn=;

ll dp[maxn],c[],d[],S,ans;

void dfs(int pos,int num,ll sum)

{

    if(pos==){

        if(sum>=) {

            if(num&) ans-=dp[sum];

            else ans+=dp[sum];

        }

        return ;

    }

    dfs(pos+,num+,sum-c[pos]*(d[pos]+));

    dfs(pos+,num,sum);

}

int main()

{

    int Q;

    rep(i,,) scanf("%lld",&c[i]);

    dp[]=;

    rep(i,,)

     rep(j,c[i],) dp[j]+=dp[j-c[i]];

    scanf("%d",&Q);

    while(Q--){

        rep(i,,) scanf("%lld",&d[i]);

        scanf("%lld",&S); ans=; dfs(,,S);

        printf("%lld\n",ans);

    }

    return ;

}

巴特西

BZOJ-1042：硬币购物（背包+容斥）

最新文章

热门文章