[洛谷 1450][HAOI2008]硬币购物

题目链接

https://www.luogu.org/problemnew/show/P1450

题解

用\(f[i]\)表示在不限制各硬币使用数量的情况下支付的方案数,这个可以用完全背包预处理出来。

接下来考虑数量限制。先从单个硬币有限制开始:我们可以推出,在第\(i\)种硬币限定取\(d[i]\)个的时候,超出该限制的方案数为\(f[s-(d[i]+1)*c[i]]\)。

这个式子的意义是明显的:我们强行让第\(i\)种硬币取\(d[i]+1\)个,剩下面额再跑完全背包得出的方案肯定是不合法的。

假如多个面额都有限制呢?简单地在总方案数上减去这几种不合法方案的数量是不合适的,因为可能有违反多个限制的方案被重复减去。

看到这里,我们想到了容斥原理。

我们将同时违反偶数个限制的方案数加上,把同时违反奇数个方案数限制的方案数减去,这些方案数的计算方法和上面单个硬币的限制是相同的。

我们可以通过二进制枚举子集来描述这样的限制。

#include <iostream>
#include <algorithm>
using namespace std;
long long c[5],d[5],f[100005],t,s;
int main()
{
 for(int i=1;i<=4;i++)
  cin>>c[i];
 cin>>t;
 f[0]=1;
 for(int i=1;i<=4;i++)
  for(int j=c[i];j<=100000;j++)
   f[j]+=f[j-c[i]];
 while(t--)
 {
  for(int i=1;i<=4;i++)
   cin>>d[i];
  cin>>s;
  long long ans=f[s];
  for(int i=1;i<=15;i++)
  {
   int x=s,tmp=i,cur=1,cnt=0;
   while(tmp)
   {
    if(tmp&1)x-=(d[cur]+1)*c[cur],cnt++;
    cur++;
    tmp>>=1;
   }
   if(x>=0)ans+=(cnt&1)?-f[x]:f[x];
  }
  cout<<ans<<endl;
 }
 return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注