P2347(NOIP1996 提高组)砝码称重 题解

题解

Step—1 命名

Step—2 暴搜

for(int i=1;i<=6;i++)
	for(int j=1;j<=a[i];j++)
		for(int x=1000;x>=0;x--)
		    if(k[x])
				k[x+f[i]]=1;
```cpp
## Step---3 统计个数
每遇到一个`k[i]=0`均`ans++`;
```cpp
for(int i=1;i<=1000;i++)
	if(k[i])
		ans++;
```cpp
# Code:
```cpp
#include<bits/stdc++.h>
using namespace std;
int a[7],f[7]={0,1,2,3,5,10,20};
bool k[1001];
int ans=0;
int main()
{
	for(int i=1;i<=6;i++)
		cin>>a[i];
	k[0]=1;
	for(int i=1;i<=6;i++)
		for(int j=1;j<=a[i];j++)
			for(int x=1000;x>=0;x--)
			    if(k[x])
					k[x+f[i]]=1;
	for(int i=1;i<=1000;i++)
		if(k[i])
			ans++;
	cout<<"Total="<<ans;
	return 0;
}