bzoj 1042: [HAOI2008]硬币购物【dp】

设f[i]为凑i元的方案数，这个随便dp一下就行了

然后处理限制，我们考虑用容斥，也就是4个超限-3个超限+2个超限-1个超限，这里用状压枚举一下，然后i硬币超限就当做选了d[i]+1个，在s里减去，最后用来容斥的就是f[s']

#include<iostream>

#include<cstdio>

using namespace std;

const long long N=100005;

long long c[10],T,d[10],s,f[N],ans;

long long read()

{

    long long r=0;

    char p=getchar();

    while(p>'9'||p<'0')

        p=getchar();

    while(p>='0'&&p<='9')

    {

        r=r*10+p-48;

        p=getchar();

    }

    return r;

}

int main()

{

    c[1]=read(),c[2]=read(),c[3]=read(),c[4]=read(),T=read();

    f[0]=1;

    for(long long j=1;j<=4;j++)

        for(long long i=1;i<=N-5;i++)

            if(i>=c[j])

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

    while(T--)

    {

        ans=0ll;

        d[1]=read(),d[2]=read(),d[3]=read(),d[4]=read(),s=read();

        for(long long i=0;i<=15;i++)

        {

            long long t=1,sum=s;

            for(long long j=1;j<=4;j++)

                if(i&(1<<(j-1)))

                {

                    t=-t;

                    sum-=(d[j]+1)*c[j];

                }

            if(sum>=0)

                ans+=t*f[sum];

        }

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

    }

    return 0;

}

巴特西

bzoj 1042: [HAOI2008]硬币购物【dp】

最新文章

热门文章