P2347（洛谷题面）

题目

题目描述：

设有 1g1\mathrm{g}、2g2\mathrm{g}、3g3\mathrm{g}、5g5\mathrm{g}、10g10\mathrm{g}、20g20\mathrm{g} 的砝码各若干枚（其总重 ），可以表示成多少种重量？

输入格式：

输入方式：a1,a2,a3,a4,a5,a6a_1 , a_2 ,a_3 , a_4 , a_5 ,a_6

（表示 1g1\mathrm{g} 砝码有 a1a_1 个，2g2\mathrm{g} 砝码有 a2a_2 个，…\dots，20g20\mathrm{g} 砝码有 a6a_6 个）

输出格式：

输出方式：Total=N

（NN 表示用这些砝码能称出的不同重量的个数，但不包括一个砝码也不用的情况）

数据范围与说明：

【题目来源】

NOIP 1996 提高组第四题

输入输出样例 #1

输入：

1
1 1 0 0 0 0

输出：

1
Total=3

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<bits/stdc++.h>
using namespace std;
int a[]={1,2,3,5,10,20};
int b[300];
int dp[1100];
int main(){
    int sum=0;
    for(int i=0;i<6;i++){
        cin>>b[i];
        sum+=a[i]*b[i];
    }
    int ans=0;
    dp[0] = 1;
    for(int i=0;i<6;i++){
        for(int j=sum;j>=0;j--){
            for (int k = 1; k <= b[i]; k++){ 
				if (dp[j - a[i]*k] == 1 && j - a[i]*k >= 0 && dp[j] == 0){
                    dp[j] = 1,ans++;
                }			
			}
        }
    }
    cout<<"Total="<<ans;
    return 0;
}