题解 P5020 【货币系统】

· · 题解

唔。。本蒟蒻在考场上以为这题又是【大凯的疑惑】这样的数竞题，果断放弃。出了考场神犇说这是完全背包。本蒟蒻就回来敲敲打打搞出了这个luogu数据95分的代码。

基本思路

首先，请看这道完全背包模板题【P1616】疯狂的采药。 将钱数从小到大排好序，然后从后往前枚举，检查这个面额是否能被更小的面额表示出来。如果可以，将该面额去掉。 可以把要表示的大面额看成【背包容量】，把小面额看成【单个物品的重量】。也就成了【完全背包】。

由于这题数据不太大，所以直接枚举貌似可以过大部分。

关键代码如下

      for(int i=n;i>=1;i--)
        {
          memset(f,0,sizeof(f));
          for(int o=1;o<i;o++)
            for(int p=a[o];p<=a[i];p++)

                f[p]=max(f[p-a[o]]+a[o],f[p])；

          if(f[a[i]]==a[i])ans--;
        }

代码呈现

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

int a[105],f[25005],t,n,ans;

int main()
{
    cin>>t;
    for(int i=1;i<=t;i++)
    {
        memset(f,0,sizeof(f));
        memset(a,0,sizeof(a));
        cin>>n;
        ans=n;
        for(int i=1;i<=n;i++)
        cin>>a[i];
        sort(a+1,a+n+1);

        for(int i=n;i>=1;i--)
        {
          memset(f,0,sizeof(f));
          for(int o=1;o<i;o++)
            for(int p=a[o];p<=a[i];p++)
                f[p]=max(f[p-a[o]]+a[o],f[p]);
          if(f[a[i]]==a[i])ans--;
        }
        cout<<ans<<endl;
    }
    return 0;
}