bzoj1042: [HAOI2008]硬币购物

Dp[i]表示硬币个数不受限制，且面额为i的方案数，那受限制的方案数就等于减去当每种硬币超过限制的方案数，又因为有重复，所以要加回来，整个过程比较抽象

const int N = 4, S = 100010;
LL Dp[S] = {0};
int Dat[N], D[N], T, s;


inline void Input() {
	Rep(i, 4) scanf("%d", &Dat[i]);
	scanf("%d", &T);
}

inline LL Dfs(int Now, bool flag, int Money) {
	if(Money < 0) return 0;
	if(Now == N) return flag & 1 ? -Dp[Money] : Dp[Money];
	return Dfs(Now + 1, flag ^ 1, Money - Dat[Now] * (D[Now] + 1)) + 
			Dfs(Now + 1, flag, Money);		
}
inline void Solve() {
	Dp[0] = 1;
	Rep(i, N)
		For(j, Dat[i], S - 1) Dp[j] += Dp[j - Dat[i]];
	
	while(T--) {
		Rep(i, N) scanf("%d", &D[i]);
		scanf("%d", &s);
		cout << Dfs(0, 0, s) << endl;
	}
}

int main() {
	Input();
	Solve();
	return 0;
}