题解 P1450 【[HAOI2008]硬币购物】

· · 题解

一道神奇的dp题,注意用longlong

首先如果同多重背包一个一个算是肯定T的 (除非你有神仙的卡常技术)

我们知道题目是要求我们用每种种类的个数有限的硬币来购买s的价值的东西的方法数,那么如果我们换一种思路,我们发现 满足要求的方法数=无限种的方法数-不满足要求(即超过限制)方法数(比如无限制有5种方法,其中3种超过了题目的限制,那么满足的就有2种)

我们先求无限种的方法数,我们设f[i]为个数无限的硬币来购买i的价值的东西的方法数,所以无限种的方法数f[s]

再来求不满足要求的(即超过限制)方法数,我们先来看第1种硬币超过要求的方法数,我们可以先强制支付(d[1]+1)个硬币,那么后面无论怎么支付第1种硬币都是超过要求的,我们知道后面要支付的钱为s-c[1]* (d[1]+1)元(就是减掉强制支付的),所以可以得到

第1种硬币超过要求的方法数=强制支付(d[1]+1)个硬币的方法数(只有一种方法)支付$s-c[1] (d[1]+1)元的方法数=支付s-c[1]* (d[1]+1)$元的方法数

即

*第1种硬币超过要求的方法数$=f[s-c[1] (d[1]+1)]$**

同理,第2种硬币超过要求的方法数=f[s-c[2]* (d[2]+1)],以此类推

但是我们直接用f[s]减掉他们得出的并不是正确的答案,因为我们看计算第1种硬币超过要求的方法数时,对于要支付的s-c[1]* (d[1]+1)元来说,并没有要求第二种硬币不超过要求,所以第一种超过要求时,第二种硬币可能同时也超过要求,同理,第二种超过要求时,第一种硬币可能同时也超过要求,这样就产生了重复(计算了两次一二同时超过要求的方法数),所以我们要再加回去一次一二同时超过要求的方法数

为了方便计算,我们用A表示第1种硬币超过要求的方法的集合,B来表示硬币2的

可能有没了解过集合的同学,所以我在这里简单说一下:

1.集合由一个或多个确定的元素所构成的整体,可以看作是“一堆东西”，集合里的“东西”则称为元素

2.交集：由属于A且属于B的元素组成的集合,就是两集合相交的部分

3.并集：由所有属于集合A或属于集合B的元素所组成的集合,就是A和B所有的元素组成的集合(重复元素的算作一个),如图

4.容斥原理:1.card(A∪B)=card(A)+card(B)-card(A∩B)(card(X)为X集合元素个数,看图理解)

集合运算满足分配对偶律：A∩(B∪C)=(A∩B)∪(A∩C)；A∪(B∩C)=(A∪B)∩(A∪C),所以

如果我们再加入一个集合C,那么(这里省略card())2.A∪B∪C=(A∪B)∪C=A+B+C-A∩B-A∩C-B∩C+A∩B∩C,直接算或看图理解

看完了上述知识点,我们可以开始计算了

对于第一种和第二种硬币,f[s]应该减掉的是card(A∪B)即card(A)+card(B)-card(A∩B)

进而对所有种类的硬币(将第3,4种硬币设为C,D),根据满足要求的方法数(即答案)=无限种的方法数-不满足要求(即超过限制)方法数

所以,

答案

=f[s]-card(A∪B∪C∪D) =f[s]-card(A)-card(B)-card(C)-card(D) +card(A∩B)+card(A∩C)+card(A∩D)+card(B∩C)+card(B∩D)+card(C∩D) -card(A∩B∩C)-card(A∩B∩D)-card(A∩C∩D)-card(B∩C∩D) +card(A∩B∩C∩D)

其中card(X∩Y∩...)的计算方法,设card内共n给集合,第i个集合代表硬币i,*所以令$K=c[1](d[1]+1)+c[2](d[2]+1)+...+c[n](d[n]+1),当k≤s时card(X∩Y∩...)=f[s-K],K>s时,card(X∩Y∩...)=0$**

我们还可以发现,当card(X∩Y∩...)内集合的个数为奇数时前面的符号为'-',为偶数时前面的符号为正,所以在程序中我们枚举所有的card()时可以通过这个来判断符号

怎么枚举,可以用二进制数来枚举(第i位为0表示这个card()中并没有硬币i,为1则有),从1(0001)枚举到15(1111)就可以了,如果你不会这种方法,直接把所有的算card的算式打上去计算结果也可以

上代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+5;
ll f[N],c[10],d[10],s;//变量意义看文章和题目
inline long long read()
{
    char c=getchar();long long sum=0,f=1;
    while(!(c>='0'&&c<='9')) {if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') {sum=((sum<<1)+(sum<<3))+(c-'0');c=getchar();}
    return sum*f;
}
int main()
{
    c[1]=read();c[2]=read();c[3]=read();c[4]=read();
    int n=read();
    f[0]=1;
    for(int i=1;i<=4;i++)
    {
        for(int j=c[i];j<=1e5;j++) f[j]+=f[j-c[i]];
    }//完全背包
    while(n--)
    {
        for(int i=1;i<=4;i++) d[i]=read();
        s=read();
        ll ans=f[s];
        for(int i=1;i<=15;i++)//枚举
        {
            ll k=0,num=0;//num用来算card内集合数量
            for(int j=0;j<4;j++)
            {
                if(i&(1<<j)) //判断第j为是否为1
                {
                    num++;
                    k+=c[j+1]*(d[j+1]+1);//算k
                }
            }
            ll fl=1;
            if(num%2) fl=-1;//判断符号
            if(s>=k) ans+=fl*f[s-k];//如果k满足条件,加(减)上
        }
        printf("%lld\n",ans);//输出
    }
    return 0;
}