BZOJ 1042 硬币购物

时间：2022-03-12 22:18:11

先不考虑限制，那么有dp[i]表示i元钱的方案数。

然后考虑限制，发现可以容斥。

其实整个题就是两个容斥原理。感觉出的蛮好的。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define maxn 100500

using namespace std;

long long f[maxn],c[],d[],n,s,ans;

void pre_dp()

{

    f[]=;

    for (long long i=;i<=maxn-;i++)

    {

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

            if (i>=c[j]) f[i]+=f[i-c[j]];

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

            for (long long k=j+;k<=;k++)

                if (i>=c[j]+c[k]) f[i]-=f[i-c[j]-c[k]];

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

            for (long long k=j+;k<=;k++)

                for (long long l=k+;l<=;l++)

                    if (i>=c[j]+c[k]+c[l]) f[i]+=f[i-c[j]-c[k]-c[l]];

        if (i>=c[]+c[]+c[]+c[]) f[i]-=f[i-c[]-c[]-c[]-c[]];

    }

}

void work()

{

    ans=;ans+=f[s];

    for (long long i=;i<=;i++) if (s>=d[i]*c[i]) ans-=f[s-d[i]*c[i]];

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

        for (long long j=i+;j<=;j++)

            if (s>=d[i]*c[i]+d[j]*c[j]) ans+=f[s-d[i]*c[i]-d[j]*c[j]];

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

        for (long long j=i+;j<=;j++)

            for (long long k=j+;k<=;k++)

                if (s>=d[i]*c[i]+d[j]*c[j]+d[k]*c[k]) ans-=f[s-d[i]*c[i]-d[j]*c[j]-d[k]*c[k]];

    if (s>=d[]*c[]+d[]*c[]+d[]*c[]+d[]*c[]) ans+=f[s-(d[]*c[]+d[]*c[]+d[]*c[]+d[]*c[])];

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

}

int main()

{

    for (long long i=;i<=;i++) scanf("%lld",&c[i]);

    scanf("%lld",&n);

    pre_dp();

    for (long long i=;i<=n;i++)

    {

        for (long long j=;j<=;j++) {scanf("%lld",&d[j]);d[j]++;}

        scanf("%lld",&s);

        work();

    }

    return ;

}

相关文章