P1450.硬币购物
题目描述
硬币购物一共有\(4\)种硬币。面值分别为\(c1,c2,c3,c4\)。某人去商店买东西，去了\(tot\)次。每次带\(d_i\)枚\(c_i\)硬币，买\(s_i\)的价值的东西。请问每次有多少种付款方法。
输入输出格式
输入格式：
第一行 \(c_1,c_2,c_3,c_4,tot\) 下面\(tot\)行 \(d_1,d_2,d_3,d_4,s\)
输出格式：
每次的方法数
说明
\(di,s<=100000\)
\(tot<=1000\)
很容易想到的，转化成多重背包
dp[0]=1;
for(int i=1;i<=4;i++)
for(int k=s;k>=0;k--)
if(dp[k])
for(int j=1;j<=a[i];j++)
dp[k+j*c[i]]+=dp[k];
printf("%d\n",dp[s]);结果当然是\(t\)飞啦
如果我们当成完全背包来做的话，当放入物品个数大于限制条件时的一部分是非法的。
假设仅仅针对价值为\(c\)的物品\(i\),存在数量上限\(d\),要凑成的钱数为\(s\).
\(dp[s]\)为装无限个\(i\)时凑成\(s\)的方案数
\(dp[s-c*(d+1)]\)为装无限个\(i\)时凑成\(s-c*(d+1)\)的方案数
相减得到什么？ 不仅是装上限为\(d\)个时的方案数吗
然而这只是针对一个物品而言，如果有多个物品呢？
存在多个约束相交的情况，那么根据容斥原理，多的减，少的回加即可。
code：
#include <cstdio>
#define ll long long
const int N=100010;
int c[5],tot,a[5],s;
ll dp[N];
int main()
{
for(int i=1;i<=4;i++) scanf("%d",c+i);
scanf("%d",&tot);
dp[0]=1;
for(int i=1;i<=4;i++)
for(int j=c[i];j<=N;j++)
dp[j]+=dp[j-c[i]];
while(tot--)
{
for(int i=1;i<=4;i++) scanf("%d",a+i);
scanf("%d",&s);
ll ans=0;
for(int i=0;i<=15;i++)
{
int flag=0,t=0;
for(int j=1;j<=4;j++)
if((i>>j-1)&1)
{
t+=c[j]*(a[j]+1);
flag^=1;
}
ll tt=(s>=t?dp[s-t]:0);
ans+=(flag?-tt:tt);
}
printf("%lld\n",ans);
}
return 0;
}注意这时候枚举子集的方法。
2018.5.4