bzoj1042: [HAOI2008]硬币购物

时间：2021-04-09 22:17:01
 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <algorithm>

 using namespace std;

 #define maxn 100005

 #define maxk 16

 int c[],tot,n,d[],num[maxk];

 typedef long long ll;

 ll f[maxn],ans;

 void read(int &x){

     x=; int f=; char ch;

     for (ch=getchar();!isdigit(ch);ch=getchar()) if (ch=='-') f=-;

     for (;isdigit(ch);ch=getchar()) x=x*+ch-''; x*=f;

 }

 ll calc(int x,int y){

     for (int i=;i<;i++) if ((x>>i)&) y-=c[i+]*(d[i+]+);

     if (y<) return ;

     if (num[x]&) return -f[y];

     else return f[y];

 }

 int lowbit(int x){return x&(-x);}

 int main(){

     for (int i=;i<;i++) num[i]=num[i-lowbit(i)]+;

     for (int i=;i<=;i++) read(c[i]);

     memset(f,,sizeof(f)),f[]=;

     for (int i=;i<=;i++){

         for (int j=c[i];j<=;j++){

             f[j]+=f[j-c[i]];

         }

     }

     read(tot);

     for (;tot;--tot){

         for (int i=;i<=;i++) read(d[i]); read(n);

         ans=; for (int i=;i<;i++) ans+=calc(i,n);

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

     }

     return ;

 }

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1042。

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

Input　第一行 c1,c2,c3,c4,tot 下面tot行 d1,d2,d3,d4,s,其中di,s<=100000,tot<=1000。

Output  每次的方法数。

做法：初看这题，对于每个询问，就是一个多重背包嘛，但是复杂度较高，过不了此题，我们发现这跟其他的背包有一点不同，就是物品只有4中，我们发现可以有指数级做法，想到了容斥原理，怎么容斥呢？显然，如果每个询问都没有限制，我们只需要O（n）的复杂度预处理，每次询问时便可以O（1）的回答了。但是怎么转化呢，这题中限制了上界不好转化，我们可以用容斥的一般式转化为补集,然后就变成了有部分变量规定了下界限制，我们在等式两边同时减去下界和即可，转化为了可以预处理出来的无限制的背包问题。容斥的注意事项，我们用一个4位的二进制数上各位的0/1来决定取还是不取，O（n）预处理出每个4位二进制数上1的个数，num[i]=num[i-lowbit(i)]+1，这很显然嘛。。

容斥原理+动态规划。

相关文章