2016.1.27 試題描述 現在一共有4種硬幣，面值各不相同，分別為ci(i=1,2,3,4)。某人去商店買東西，去了tot次，每次帶di枚ci硬幣，購買價值為si的貨物。請問每次有多少種付款方法。 輸入 第一行包括五個數，分別為c1,c2,c3,c4和tot 接下來有tot行，每行五個數，第i+
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
