BZOJ 1042 硬币购物

先不考虑限制,那么有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 ;
}
上一篇:JAVA类与对象(八)-----重写


下一篇:linux 入侵检查转载