如果要专门地去证明b中的元素都是a中选取的可能会有点困难,这里提供一个比较简单的思考方向。
约定记号:
vis[x] = true
表示x
能够被当前b中的元素表示出
朴素的想法是先将a从小到大排序,记a最小的元素为mina
,
分析
我们能够比较简单地知道b中必含有mina
:
显然如果b中含有比mina
小的元素,那么这个元素对应的数是a所能组成的数的空间所没有的,与题意不符,同时,倘若b中的元素都比mina
大,那么b所能组成的数的空间一定不包含mina
,也矛盾。
所以b中第一个元素就是mina
此时,我们可以更新一下vis
数组:将vis[mina*k] (k为正整数)
全部标记为true
接下来,继续考察排好序的a:
如果a的第二个数x
对应的vis[x]
是true
,那么自然不需要进入b中(而且这样不是最优解)。
如果a的第二个数x
对应的vis[x]
是false
那么一定要进入b中:
因为如果不进入:
那么我们必须要找到一个数val
(进入b中)使得mina+k*val=x
,那么此时val
一定是小于x
的,故vis[val] = true
,而a所能组成的数的空间不包含val
,矛盾。
按照这样的策略,可以依次将a中的元素放入b中。
#include<bits/stdc++.h>
using namespace std;
const int N = 50005;
int n;
bool vis[N];
int a[105];
int main(){
int T; cin>>T;
while(T--){
memset(vis,0,sizeof vis);
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+1+n);
int maxv=-1;
for(int i=1;i<=n;i++) maxv=max(maxv,a[i]);
int cnt=0;
for(int i=1;i<=n;i++){
if(vis[a[i]]) continue;
else cnt++;
for(int j=0;j<=maxv;j++)
if(vis[j]) vis[j+a[i]]=1;
for(int j=a[i];j<=maxv;j+=a[i]) vis[j]=1;
}
cout<<cnt<<endl;
}
}
妙啊