【BZOJ 1042】[HAOI2008] 硬币购物

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1042

这个题呢，第一眼看到就知道不会做，结果果然只会O(n*logn*t)的dp
题解的话，我们来膜byvoid吧：https://www.byvoid.com/blog/haoi-2008-coin

#include<iostream>
#include<cstdio>
#define LL long long
using namespace std;

const int SGZ = 5;
const int MAXN = 100000+9;
const int LIM = 100000;

int c[SGZ],s,d[SGZ];
LL f[MAXN],vout;

inline int read(){
	char c=getchar(); int ret = 0;
	while (c<'0'||c>'9') c=getchar();
	while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
	return ret;
}

void solve(int p, int sz, int w){
	if (p == 5) {
		if (sz & 1) vout -= f[s-w];
		else if (sz) vout += f[s-w];
	} else {
		solve(p+1,sz,w);
		if (w+d[p] <= s) solve(p+1,sz+1,w+d[p]);
	}
}

int main(){
	for (int i=1;i<=4;i++) c[i] = read(); int T = read(); f[0] = 1;
	for (int j=1;j<=4;j++) for (int i=c[j];i<=LIM;i++) f[i] += f[i-c[j]];
	while (T--) {
		for (int i=1;i<=4;i++) d[i] = read(); s = read();
		for (int i=1;i<=4;i++) d[i] = (d[i]+1)*c[i];
		vout = f[s]; solve(1,0,0);
		printf("%lld\n",vout);	
	}
	return 0;
}