洛谷 P2347 砝码称重 != codevs 2144

题目描述

设有1g、2g、3g、5g、10g、20g的砝码各若干枚（其总重<=1000），

输入输出格式

输入格式：

输入方式：a1 a2 a3 a4 a5 a6

（表示1g砝码有a1个，2g砝码有a2个，…，20g砝码有a6个）

输出格式：

输出方式：Total=N

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

输入输出样例

输入样例#1：

1 1 0 0 0 0

输出样例#1：

Total=3

砝码只有选与不选 所以是01背包 

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;

bool fw[];

int h=,a1,a2,a3,a4,a5,a6;

int a[],ans,i,j,dp[];

int main()

{

    cin>>a1>>a2>>a3>>a4>>a5>>a6;

    while(a1--)

    a[h++]=;

    while(a2--)

    a[h++]=;

    while(a3--)

    a[h++]=;

    while(a4--)

    a[h++]=;

    while(a5--)

    a[h++]=;

    while(a6--)

    a[h++]=;

    for(i=;i<h;++i)

    {

        for(j=;j>=a[i];--j)//题目说总重不超过1000

        dp[j]=max(dp[j],dp[j-a[i]]+a[i]);

    }

    for(i=;i<=;++i)//累加不同情况

    if(dp[i]&&!fw[dp[i]])

    {

        fw[dp[i]]=;

        ans++;

    }

    cout<<"Total="<<ans;

}