题解 P2347 【砝码称重】

· · 题解

想到一种稍微简单的方法，思想类似于装箱问题；

先打一个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即为所有情况数；

附上代码

#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;
}