1714 - 砝码称重
设有1g，2g，3g，5g，10g，20g的砝码各若干枚（其总重≤1000g），编程求出能称出重量的个数。
Input
a1 a2 a3 a4 a5 a6(分别表示1g砝码有a1个，2g砝码有a2个，......20g砝码有a6个)
Output
一行：一个整数（表示用这些砝码能称出的不同重量的个数，但不包括一个砝码也不用的情况）
Examples
Input
1 1 0 0 0 0
Output
3
Solution C
#include "stdio.h" int a[]={1,2,3,5,10,20}; int b[6],f[1001]; int t,s; int main() { int i,j,k; s=t=0; for(i=0;i<6;i++) { scanf("%d",&b[i]); s+=a[i]*b[i]; } f[0]=1; for(i=0;i<6;i++) { if(b[i]==0) continue; k=1; while(k<b[i]) { for(j=s;j>=k*a[i];j--) { if(f[j]) continue; if(f[j-k*a[i]]) f[j]=1,t++; } b[i]-=k; k*=2; } k=b[i]; for(j=s;j>=k*a[i];j--) { if(f[j]) continue; if(f[j-k*a[i]]) f[j]=1,t++; } } printf("%d\n",t); return 0; }
Solution C++
#include<iostream> using namespace std; const int w[7]={0,1,2,3,5,10,20}; int num[7],f[1001]; bool can[1001]; //ifstream cin("fama.in"); //ofstream cout("fama.out"); int main() { while (cin>>num[1]>>num[2]>>num[3]>>num[4]>>num[5]>>num[6]) { fill(can,can+1001,0); f[0]=1; f[1]=0; can[0]=true; for (int i=1;i<=6;i++) { int total=f[0]; //已经求出的重量数量 for (int j=1;j<=total;j++) for (int k=1;k<=num[i];k++) if (!can[f[j]+k*w[i]]) { can[f[j]+k*w[i]]=true; f[0]++; f[f[0]]=f[j]+k*w[i]; } } cout<<f[0]-1<<endl; } // system("pause"); return 0; }