洛谷P2347 砝码称重

 1 #include<bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 bool dp[10005];
 6 
 7 int a,weight[7]={0,1,2,3,5,10,20},tot,v[10005],ans; 
 8 
 9 inline int read(void){
10     int x=0,f=1;char ch=getchar();
11     while(ch<‘0‘||ch>‘9‘){
12         if(ch==‘-‘) f=-1;
13         ch=getchar();
14     }
15     while(ch>=‘0‘&&ch<=‘9‘){
16         x=(x<<1)+(x<<3)+ch-‘0‘;
17         ch=getchar();
18     }
19     return x*f;
20 }
21 
22 void cf(int x,int y){
23     for(register int i=1;x-i>=0;i<<=1)
24         v[++tot]=weight[y]*i,x-=i;
25     if(x) v[++tot]=weight[y]*x;
26 }
27 
28 int main(){
29     for(register int i=1;i<=6;i++)
30         a=read(),cf(a,i);
31     dp[0]=1;
32     for(register int i=1;i<=tot;i++)
33         for(register int j=10000-v[i];j>=0;j--)
34             dp[j+v[i]]|=dp[j];
35     for(register int i=1;i<=10000;i++)
36         if(dp[i]) ans++;
37     printf("Total=%d\n",ans);
38     return 0;
39 }