洛谷 P1450 [HAOI2008] 硬币购物

本文主要是介绍洛谷 P1450 [HAOI2008] 硬币购物，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

思路

完全背包：预处理出不限制硬币数量的方案数。

dp[0]=1;
dfor(i,1,4) dfor(j,c[i],(int)1e5) dp[j]+=dp[j-c[i]];

容斥

不限制数量的方案数 $-$ 超出限制的方案数 = 符合限制的方案数 。考虑第 $i$ 种硬币超出数量限制的方案数。强制支付 $d_i+1$ 个 $i$ 种硬币，价值为 $c_i*(d_i+1)$ ，此时再支付硬币 $i$ 一定是超出限制的。得：超出硬币 $i$ 限制的价值为 $s-c_i*(d_i+1)$ ，方案数为 $dp[s-c_i*(d_i+1)]$ 。
上述得出超出硬币 $i$ 价值为 $s-c_i*(d_i+1)$ ，这只是一种硬币的情况，如果不止一种硬币，你无法保证价值 $s-c_i*(d_i+1)$ 中是否包含了硬币 $j$ 的符合限制的价值，也就是说 $dp[s-c_i*(d_i+1)]$ 中有硬币 $j$ 符合限制的方案数。
硬币 $i$ 超出限制集合表示为 $A_i$ ，硬币 $j$ 超出限制集合表示为 $A_j$ ， $A_i\cup A_j=A_i+A_j-A_i\cap A_j$ ~~不多说奇加偶减~~ 。不限制集合设为 $S$ ，答案集合 $ans=S-(A_i\cup A_j\cup \ldots)$ 。

二进制

用每一位表示一种硬币， $1$ 那一位存在硬币， $0$ 反之。如 $0101$ 表示第 $3$ 种硬币和第 $1$ 种的并集。

dfor(i,1,15)
{re int cnt=0,sum=0;dfor(j,0,3)if(i&(1<<j)) ++cnt,sum+=c[j+1]*(d[j+1]+1);int f=cnt&1?-1:1;if(s>=sum) ans+=f*dp[s-sum];
}

Think Twice, Code Once

#include<bits/stdc++.h>
#define il inline
#define get getchar
#define put putchar
#define is isdigit
#define re register
#define int long long
#define dfor(i,a,b) for(re int i=a;i<=b;++i)
#define dforr(i,a,b) for(re int i=a;i>=b;--i)
#define dforn(i,a,b) for(re int i=a;i<=b;++i,put(10))
#define mem(a,b) memset(a,b,sizeof a)
#define memc(a,b) memcpy(a,b,sizeof a)
#define pr 114514191981
#define gg(a) cout<<a,put(32)
#define INF 0x7fffffff
#define tt(x) cout<<x<<'\n'
#define ls i<<1
#define rs i<<1|1
#define la(r) tr[r].ch[0]
#define ra(r) tr[r].ch[1]
#define lowbit(x) (x&-x)
using namespace std;
typedef unsigned int ull;
int read(void)
{re int x=0,f=1;re char c=get();while(!is(c)) (f=c==45?-1:1),c=get();while(is(c)) x=(x<<1)+(x<<3)+(c^48),c=get();return x*f;
}
void write(int x)
{if(x<0) x=-x,put(45);if(x>9) write(x/10);put((x%10)^48);
}
#define writeln(a) write(a),put(10)
#define writesp(a) write(a),put(32)
#define writessp(a) put(32),write(a)
const int N=1e5+10,M=3e4+10,SN=1e4+10,mod=998244353;
int n,s,c[5],d[5],dp[N];
signed main()
{dfor(i,1,4) c[i]=read();n=read();dp[0]=1;dfor(i,1,4) dfor(j,c[i],(int)1e5) dp[j]+=dp[j-c[i]];while(n--){dfor(i,1,4) d[i]=read();s=read();re int ans=dp[s];dfor(i,1,15){re int cnt=0,sum=0;dfor(j,0,3)if(i&(1<<j)) ++cnt,sum+=c[j+1]*(d[j+1]+1);int f=cnt&1?-1:1;if(s>=sum) ans+=f*dp[s-sum];}writeln(ans);}return 0;
}