BZOJ1042 「HNOI2008」硬币购物

Description

一共有 $4$ 种硬币。面值分别为 $c_1,c_2,c_3,c_4$ 。某人去商店买东西，去了 $tot$ 次。每次带 $d_i$ 枚 $c_i$ 硬币，买 $s$ 的价值的东西。请问每次有多少种付款方法。

Solution

考虑没有 $d$ 的限制，直接完全背包。$dp_i$ 表示 $i$ 这个面值用 $c_1…c_4$ 凑有多少种方法

加上限制就容斥枚举 $16$ 种情况表示哪几种面值的性质没有被满足。

然后可以观察到，如果对于 $i$ 不满足限制，方案数就是 $dp_{s-(d_i+1)c_i}$

所以归纳一下就是

$$ans = \sum\limits_{S \subseteq {1,2,3,4}}(-1)^{|S|}dp_{(s-\sum\limits_{x \in S} (d_x+1)c_x)}$$

Code

/**
 * Author: AcFunction
 * Date:   2019-03-04 17:57:01
 * Email:  3486942970@qq.com
**/
 
#include <bits/stdc++.h>
#define int long long
#define ll long long
#define RG register 
#define rep(i, l, r) for(RG int i = l; i <= r; i++) 
#define per(i, r, l) for(RG int i = r; i >= l; i--)
 
using namespace std;
 
void INIT() {
  ios :: sync_with_stdio(false); cin.tie(0); 
}
 
const int N = 100100; 
 
int n, c[5], d[5]; int dp[N]; 
signed main() {
  INIT(); dp[0] = 1; 
  rep(i, 1, 4) cin >> c[i]; cin >> n; 
  rep(j, 1, 4) rep(i, 0, 100000)
      if(i + c[j] <= 100000) 
        dp[i + c[j]] += dp[i]; 
  rep(i, 1, n) { int s; int ans = 0; 
    rep(j, 1, 4) cin >> d[j]; cin >> s;  
    rep(j, 0, 15) {
      int s1 = 0, s2 = s; 
      rep(t, 1, 4) 
        if(j & (1 << (t - 1))) {
          s1++; s2 -= (d[t] + 1) * c[t]; 
        }
      ans += ((s1 & 1) ? -1 : 1) * (s2 >= 0 ? dp[s2] : 0); 
    }  cout << ans << endl; 
  }
  return 0; 
}