题解 P5020 【货币系统】

Update:2020.3.12更新排版。已退役。 相关证明前面各位$\large{\textbf{大佬}}$讲的很完备了，这里就不说了。 简单讲一下思路吧。看到很多人说用完全背包，我决得大可不必。大部分人应该做过（或至少听说过）[丑数](https://www.luogu.org/problem/UVA136)这道题吧(没听说过的请先去看题)。一个很好的思路就是用和丑数类似的筛法去筛，如果能被筛到那就去掉。这样代码比用背包的好写些（虽然效率会略低但还是可以接受不会TLE）。~~其实是我太水了背包都忘了还去打提高组~~。 代码： ```cpp #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说这题还可以用扩欧去做，比我这个还要快？留给大家思考 ~~(我怎么会说其实是我不大清楚具体怎么实现)~~ 。我实在是太水了，大概要退役了。(Update:已退役)