【bzoj】1042: [HAOI2008]硬币购物

比眉伴天荒 2022-09-30 15:59 135阅读 0赞

1042: \[HAOI2008\]硬币购物

Time Limit: 10 Sec Memory Limit: 162 MB  
Submit: 2371 Solved: 1416  
\[Submit\]\[Status\]\[Discuss\]  
Description

硬币购物一共有4种硬币。面值分别为c1,c2,c3,c4。某人去商店买东西，去了tot次。每次带di枚ci硬币，买s  
i的价值的东西。请问每次有多少种付款方法。

Input

第一行 c1,c2,c3,c4,tot 下面tot行 d1,d2,d3,d4,s,其中di,s<=100000,tot<=1000

Output

每次的方法数

Sample Input

1 2 5 10 2

3 2 3 1 10

1000 2 2 2 900  
Sample Output

### 题解： ###

### 设F\[i\]为不考虑每种硬币的数量限制的情况下，得到面值i的方案数。则状态转移方程为 ###

### F\[i\]=Sum\{F\[i-C\[k\]\] | i-C\[k\]>=0 且 k=1..4\} ###

### 对于某种硬币ci，超过数量限制的方案数为f(s−(di+1)×ci) ###

### 最终方案=总方案(无限制的方案)-1种硬币超限方案+2种硬币超限方案-3种硬币超限方案+4种硬币超限方案 ###

#include <iostream>
    #include <iomanip>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <cmath>
    using namespace std;
    typedef long long LL;
    
    LL ans,vis[100000+5];
    int c[4],d[4],tot,s;
    
    void dfs(int x,int k,int sum)
    {
        if(sum<0)
            return;
        if(x == 4)
        {
            if(k&1)
                ans -= vis[sum];
            else ans += vis[sum];
            return;
        }
        dfs(x+1,k+1,sum-(d[x]+1)*c[x]);
        dfs(x+1,k,sum);
    }
    inline int read()
    {
        int x=0;char ch=getchar();
        while(ch<'0'||ch>'9')ch=getchar();
        while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
        return x;
    }
    int main()
    {
        for(int i=0;i<4;i++)
            c[i]=read();
        tot = read();
        vis[0] = 1;
        for(int i=0;i<4;i++)
            for(int j=c[i];j<=100000;j++)
            vis[j] +=vis[j-c[i]];
            while(tot--)
            {
                for(int i=0;i<4;i++)
                d[i]=read();
                s = read();
                ans =0;
                dfs(0,0,s);
                cout<<ans<<endl;
            }
        return 0;
    }