P2347 砝码称重

P2347 砝码称重

题解

首先我们把这些砝码一个一个的摆出来

    for(int i=1;i<=6;i++)
    {
        x=read();
        for(int j=1;j<=x;j++) a[++cnt]=ma[i];
    }

然后数组 f[i] 记录 i 这个质量能不能摆出来，显然 f [0] 可以

如果这个质量可以摆出来的话，那么在此基础上加上一个砝码，那么 新的质量也是可到达的

      for(int i=1;i<=cnt;i++)
      for(int j=1000;j>=0;j--)
         if(f[j]) f[j+a[i]]=1;

最后统计一下哪些质量可以摆出来，就是答案了

代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<string>
#include<cstring>
#include<cstdlib>
#include<queue>

using namespace std;

inline int read()
{
    int ans=0;
    char last=' ',ch=getchar();
    while(ch<'0'||ch>'9') last=ch,ch=getchar();
    while(ch>='0'&&ch<='9') ans=ans*10+ch-'0',ch=getchar();
    if(last=='-') ans=-ans;
    return ans;
}

int ma[7]={0,1,2,3,5,10,20};
int a[1010],cnt=0,ans=0;
bool f[1010];

int main()
{
    int x;
    for(int i=1;i<=6;i++)
    {
        x=read();
        for(int j=1;j<=x;j++) a[++cnt]=ma[i];
    }
    f[0]=1;
    for(int i=1;i<=cnt;i++)
      for(int j=1000;j>=0;j--)
         if(f[j]) f[j+a[i]]=1;
    for(int i=1;i<=1000;i++)
      if(f[i]) ans++;
    printf("Total=%d
",ans);
    return 0;
}