题解 P5020 【货币系统】

· · 题解

题目名称：货币系统

来源：2018年NOIP提高组

链接

博客链接

题目链接

题目大意

已知货币系统(n,a)，n表示有多少种面额，a是一个集合，各个元素表示各种面额的大小。

两个货币系统(n,a)和(m,b)是等价的，当且仅当对于任意非负整数x，它要么均可以被两个货币系统表出，要么不能被其中任何一个表出。

找到一个货币系统(m,b)，满足(m,b)与原来的货币系统(n,a)等价，且m尽可能的小。其中b\in a。

提示

因为钱掉进了水里，所以这是一道水题。

题解

输入每种面额后，先将其从小到大排序。

引理

如果一个面额无法被比它小的面额凑出来，那么必须选，否则一定不选。

证明：前者很显然，因为这个数不可能被比其更大的数凑出来。

后者，因为这个数可以被其他数凑出来，那么需要这个数组成的数只需要凑成这个数的数就可以了。

于是我们按顺序做完全背包，如果发现没被前面的数背包得到就选，否则不选。

//C++
#include<bits/locale_facets.h>
#include<memory.h>
#include<stdio.h>
using namespace std;
inline void output(long long value);
inline long long input();
short a[101],able[25001];
int main()
{
    short T=input();
    while(T--)
    {
        short n=input(),maximum=0;
        short must=n;
        for(short i=1;i<=n;i++)maximum=max(maximum,a[i]=input());
        able[0]=true;
        for(short i=1;i<=n;i++)
        for(short j=a[i];j<=maximum;j++)
        if(able[j-a[i]])able[j]++;
        for(short i=1;i<=n;i++)
        if(able[a[i]]>1)must--;
        memset(able,0,50002);
        output(must),putchar('\n');
    }
    return 0;
}
inline void output(long long o)
{
    if(o<0)putchar('-'),o=-o;
    if(o>=10)output(o/10);
    putchar(o%10^'0');
}
inline long long input()
{
    bool positive=true;
    char now=getchar();
    long long i=0;
    for(;!isdigit(now);now=getchar())
    if(now=='-')positive=!positive;
    for(;isdigit(now);now=getchar())i=(i<<3)+(i<<1)+(now^'0');
    return positive?i:-i;
}