【题解】P2347

P2347（洛谷题面）

题目

题目描述：

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

输入格式：

输入方式：$a_1 , a_2 ,a_3 , a_4 , a_5 ,a_6$

（表示 $1\mathrm{g}$ 砝码有 $a_1$ 个，$2\mathrm{g}$ 砝码有 $a_2$ 个，$\dots$，$20\mathrm{g}$ 砝码有 $a_6$ 个）

输出格式：

输出方式：Total=N

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

数据范围与说明：

【题目来源】

NOIP 1996 提高组第四题

输入输出样例 #1

输入：

1 1 0 0 0 0

输出：

Total=3

代码

#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;
}