硬幣購物，硬幣錯印釘子上
2016.1.27
試題描述
現在一共有4種硬幣，面值各不相同，分別為ci(i=1,2,3,4)。某人去商店買東西，去了tot次，每次帶di枚ci硬幣，購買價值為si的貨物。請問每次有多少種付款方法。
輸入
第一行包括五個數，分別為c1,c2,c3,c4和tot 接下來有tot行，每行五個數，第i+1行五個數依次為第i次購物所帶四種硬幣的數目和購買貨物的價值（d1,d2,d3,d4,s ）。各行的數兩兩之間用一個空格分隔。
輸出
一行，包括tot個數，依次為每次付款的方法數。兩數之間用一個空格分隔。
輸入示例
1 2 5 10 2
3 2 3 1 10
1000 2 2 2 900
輸出示例
4 27
其他說明
數據范圍：0<di,s<=100000,0<tot<=1000，數據面值最大不超過20，所給數據保證每次至少有一種付款方法。
hzwer給的容斥原理解法
先預處理出達到面值s的方法，不考慮硬幣是否超過限制。這個用簡單背包就好。
然後從裡面扣出有至少一枚硬幣超過限制的方法即是答案。
又有：至少一枚硬幣超限=第一種硬幣超限+第二種硬幣超限+第三種硬幣超限+第四種硬幣超限-第一種和第二種都超限-第一種和第三種都超限-第一種和第四種都超限-第二種和第三種都超限-第二種和第四種都超限-第三種和第四種都超限+......-四種都超限
然後就狀壓容斥
若第一種硬幣超限，則f[s-(d[1]+1)*c[1]]即為方案數，因為保證了多用一次第一種硬幣。以此類推
注意判sum超s的情況
AC代碼：
![]()
#include<iostream>
using namespace std;
int c[5],tot,d[5],s,ct,sum,flag;
long long f[100005],ans;
int main()
{
for(int i=1;i<=4;i++) scanf("%d",&c[i]);
scanf("%d",&tot);
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(tot--)
{
for(int i=1;i<=4;i++) scanf("%d",&d[i]);
scanf("%d",&s);
ans=0;
for(int i = (1 << 4) - 1 ; i >= 0 ; i-- )
{
ct=0;sum=0;
for(int j = 3 ; j >= 0 ; j-- )
{
if(1<<j & i) ct++,sum+=(d[j+1]+1)*c[j+1];
}
if(s<sum) continue;
if(ct & 1) ans-=f[s-sum];
else ans+=f[s-sum];
}
if(flag) cout<<" ";
flag=1;
cout<<ans;
}
}
View Code
