luogu 5020

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

现在网友们打算简化一下货币系统。他们希望找到一个货币系统 (m,b)(m,b)，满足 (m,b)(m,b) 与原来的货币系统 (n,a)(n,a) 等价，且 m 尽可能的小。他们希望你来协助完成这个艰巨的任务：找到最小的 m

背包，很明显了

据猜测和观察样例，应该是看对于任意 a[i] 是否可以被其他货币表示出来

#include 
#include 
using namespace std ;const int M=3e4,N=102;int n,a[N],f[M+5];void solve(){int i,j;cin>>n;for(i=1;i<=n;i++) cin>>a[i];memset(f,0,sizeof f);f[0]=1;for(i=1;i<=n;i++)for(j=a[i];j<=M;j++)f[j]+=f[j-a[i]];int t=0;for(i=1;i<=n;i++) if(f[a[i]]>1) t++;cout<>cas;while(cas--){solve();}}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！