题解 P2347 【砝码称重】
ysy666
2017-08-25 09:38:44
想到一种稍微简单的方法，思想类似于装箱问题；
先打一个b[10]={0,1,2,3,5,10,20}；
再用a数组记录展开后的a1个1g，a2个2g。。
举个栗子：2 1 2 1 1 1存在a里就是1 1 2 3 3 5 10 20 ；
a数组里元素个数为a1~a6的和，记为num
从1到num扫一遍，把所有可能出现的情况在一个bool数组中标记出来；
最后从v到0跑一遍，找到的一个非零的值ans++；
跑完之后ans即为所有情况数；
附上代码
```cpp
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int a[10010],x,num,b[10]={0,1,2,3,5,10,20},ans;
bool t[10010];
int main()
{
for(int i=1;i<=6;i++)
{
cin>>x;
for(int j=1;j<=x;j++) a[++num]=b[i]; //在a数组里记录所有砝码重
}
t[0]=1;
for(int i=1;i<=num;i++) //num即为a数组中元素的个数
for(int j=1010;j>=0;j--) if(t[j]) t[j+a[i]]=1;
//这里一定从最大称重跑到0，否则新出现的情况会影响到后面的记录
for(int i=1;i<=1010;i++) if(t[i]) ans++; //如果某一位为true说明可能出现这种情况
printf("Total=%d",ans);
return 0;
}
```