HAOI 硬幣購物，haoi硬幣購物

HAOI 硬幣購物，haoi硬幣購物

試題描述：

現在一共有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。

這道題其實就是一個dp+容斥原理(不知道什麼是容斥原理的自己上網百度去)…… 

首先我們先對於dp數組進行初始操作。我們定義：dp[i]是在不考慮硬幣是否超限的情況下用硬幣湊i元的方案數。這樣我們就可以得到狀態方程：dp[j]+=dp[j-c[i]](由數據發現我們的0<=j<=100000，1<=i<=4)注意：dp[0]=1

然後我們就可以進行容斥原理的操作。對於每種硬幣，都有超和不超兩種情況，所以最終我們只需要統計2^4=16次就夠了。在記錄狀態的時候，我們可以用10進制的數來記錄，可是在操作的時候其實是對2進制進行操作。舉個例子：比如我用5記錄了一種狀態，5的二進制就是0101，其表達的意思就是第一種和第三種硬幣超出了限度。

那麼我們應該如何來表示使用硬幣超過了限度？舉個例子：比如當前第i種硬幣有d[i]枚硬幣可以用的話，如果我們用到了d[i]+1枚硬幣那就是說我們用硬幣超過了限度，且其他硬幣是可以隨意使用的，所以這樣的情況應該有dp[s-c[i]*(d[i]+1)]種，如果s-c[i]*(d[i]+1)<0那方案數也就是0。其余的情況也類似。

這題是要開long long的，要不過不去……我就是這麼死的……

AC代碼：

#include<iostream>
#include<memory.h>
#include<stdio.h>
#include<cstdio>
#include<cctype>
using namespace std;
//--------------------------
void read(long long &x){
    x=0;char ch=getchar();long long f=1;
    for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';
    x*=f;
}
//---------------------------
long long c[5],d[5],s,tot,ans,cnt,sum,cur;
long long dp[100000+10];
bool flag=0;
int main(){
    for(int i=1;i<=4;i++){
        read(c[i]);
    }
    read(tot); 
    dp[0]=1;
    for(int i=1;i<=4;i++){
        for(int j=c[i];j<=100000;j++)dp[j]+=dp[j-c[i]];
    }
    while(tot--){
        for(int i=1;i<=4;i++)read(d[i]);
        read(s);
        ans=0;
        for(int i=0;i<16;i++){
            cnt=0;sum=0;cur=0;
            int t=i;
            while(t>0){
                cur++;
                if(t&1)sum+=(d[cur]+1)*c[cur],cnt++;
                t>>=1;
            }
            if(s<sum)continue;
            if(cnt&1)ans-=dp[s-sum];
            else ans+=dp[s-sum];
        }
        printf("%lld\n",ans);
    }
}