BZOJ 1042 硬币购物

 1 #include<cstdio>
 2 #include<cstdlib>
 3 using namespace std;
 4  
 5 #define maxn 100010
 6 int T,c[5],d[5],save[5],s;
 7 long long f[maxn],ans;
 8  
 9 inline void ready()
10 {
11     f[0] = 1;
12     for (int i = 1;i <= 4;++i) for (int j = c[i];j < maxn;++j) f[j] += f[j-c[i]];
13 }
14  
15 inline void dfs(int a,int cho)
16 {
17     if (a > 4)
18     {
19         int dec = 0; long long ff;
20         for (int i = 1;i <= cho;++i)
21         {
22             dec += c[save[i]]*(d[save[i]]+1);
23             if (dec > s) return;
24         }       
25         if (cho & 1) ff = -1; else ff = 1;
26         ans += ff*f[s-dec];
27         return;
28     }
29     dfs(a+1,cho);
30     save[cho+1] = a;
31     dfs(a+1,cho+1);
32 }
33  
34 int main()
35 {
36     freopen("1042.in","r",stdin);
37     freopen("1042.out","w",stdout);
38     for (int i = 1;i <= 4;++i) scanf("%d",c+i);
39     scanf("%d",&T);
40     ready();
41     while (T--)
42     {
43         for (int i = 1;i <= 4;++i) scanf("%d",d+i);
44         scanf("%d",&s);
45         ans = 0; dfs(1,0);
46         printf("%lld\n",ans);
47     }
48     return 0;
49 }