【SSL】1072砝码称重

Time Limit:1000MS
Memory Limit:65536K

Description

设有1g、2g、3g、5g、10g、20g的砝码各若干枚（其总重<=1000），
要求：
输入方式：a1 a2 a3 a4 a5 a6
（表示1g砝码有a1个，2g砝码有a2个，…，20g砝码有a6个）
输出方式：N
（N表示用这些砝码能称出的不同重量的个数，但不包括一个砝码也不用的情况）

Input

Output

Sample Input

1 1 0 0 0 0
(注：下划线表示空格）

Sample Output

3 表示可以称出1g，2g，3g三种不同的重量。

思路

这是一道。
把每一个砝码都做01背包。
设f[i]表示ig是否能被称出来。
f[i]=f[i]|f[i-a[j]]，f[0]=1,1<=i<=1000,1<=j<=6
最后再扫一次。

代码

#include<iostream>#include<cstdio>#include<cstring> using namespace std;bool f[1010];int main(){   	int a[10]={   0,1,2,3,5,10,20},i,j,k,ans=0,t;	memset(f,0,sizeof(f));	f[0]=1;	for(i=1;i<=6;i++)	{   		scanf("%d",&t);		for(j=1;j<=t;j++)			for(k=1000;k>0;k--)				if (k>=a[i])					f[k]|=f[k-a[i]];//状态转移方程	}	for(i=1;i<=1000;i++)		ans+=f[i];	printf("%d",ans);	return 0;}