题解 P5020 【货币系统】

相关证明前面各位 $\mathtt{\text{大佬}}$ 讲的很完备了,这里就不说了。
简单讲一下思路吧。看到很多人说用完全背包,我决得大可不必。大部分人应该做过(或至少听说过)丑数这道题吧(没听说过的请先去看题)。一个很好的思路就是用和丑数类似的筛法去筛,如果能被筛到那就去掉。这样代码比用背包的好写些(虽然效率会略低但还是可以接受不会TLE)。其实是我太水了背包都忘了还去打提高组
代码:

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    register char ch=getchar();
    register int x=0;
    while(ch>'9'||ch<'0')ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-'0',ch=getchar();
    return x;
}
void print(int x)
{
    (x>9)&&(print(x/10),true);
    putchar(x%10+48);
}
int a[105],n;
bool can[50005];
bool find_(int x)
{
    for(int i=1;i<=n;i++)if(a[i]==x)return 1;
    return 0; 
}
int main()
{
    int t=read();
    while(t--)
        {
            int cnt=0;
            memset(can,0,sizeof can);
            n=read();
            for(int i=1;i<=n;i++)a[i]=read();
            for(int i=1;i<=25000;i++)
                if(can[i])for(int j=1;j<=n;j++)can[i+a[j]]=1;
                else if(find_(i))
                    {
                        cnt++;
                        for(int j=1;j<=n;j++)can[i+a[j]]=1;
                    }
            print(cnt);
            putchar('\n');
        }
}

另外,听一个大佬@team096说这题还可以用扩欧去做,比我这个还要快?留给大家思考 (我怎么会说其实是我不大清楚具体怎么实现) 。我实在是太水了,大概要退役了。


发表于 2019-08-08 17:14:28 in 题解