洛谷 P2347 砝码称重

 1 #include<cstdio>
 2 #include<iostream>
 3 
 4 using namespace std;
 5 
 6 int a[10], w[10] = {0, 1, 2, 3, 5, 10, 20};
 7 int dp[10005], ans;
 8 
 9 int main(){
10     for(int i = 1; i <= 6; i++)    
11         scanf("%d", &a[i]);
12     dp[0] = 1;
13     for(int i = 1; i <= 6; i++){
14         for(int j = 1; j <= a[i]; j++){
15             for(int k = 1000; k >= 0; k--){
16                 if(dp[k] && k + w[i] <= 1000){
17                     dp[k + w[i]] = 1;//打标记 
18                 }
19             }
20         }
21     }
22     for(int i = 1; i <= 1000; i++){
23         if(dp[i]) ans++;
24     }
25     printf("Total=%d", ans);
26     return 0;
27 }