题解 P5020 【货币系统】

shenbear · 2019-11-03 15:33:39 · 题解

大致想了一下,发现这是一个类似完全背包的问题

首先摆出结论,将可以由前面组成的面值删去

对于这些面值,反正我能用前面的钱组成,我把前面的钱当这个面值就可以了,所以原来能组成那些面值不受影响;同理,原来比他大的值不能组成的也不受影响,而比他小面值的肯定不会被他影响

有了这个结论,就好办了

我们用一个完全背包来转移前面的面值能组成那些后面的面值

具体看代码

#include <bits/stdc++.h>
using namespace std;
int t,n,a[222],f[25005],b[222]; //b[j]:j位置有无被筛掉，f[j]:j价值是否可以被前i个货币组成(完全背包滚掉第一位) 
void init() //初始化 
{
    memset(b,0,sizeof(b));
    memset(f,0,sizeof(f));
}
int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n;
        int s=n; //开始没有被筛掉 
    //  printf("#%d\n",s);
        init();
        for(int i=1;i<=n;i++) scanf("%d",a+i);
        sort(a+1,a+1+n);
        f[0]=1;//0当然可以 
        for(int i=1;i<=n;i++)
        {
            if(b[i]) continue;
            for(int j=a[i];j<=a[n];j++) f[j]|=f[j-a[i]];//完全背包 
            for(int j=i+1;j<=n;j++) if(f[a[j]]&&!b[j]) //如果后面的可以由前面的组成 
            {
                b[j]=1; //标记 
                s--; //需要数-- 
            }
        }
        printf("%d\n",s);
    }
    return 0;
}