一个手动枚举能过一半点而且基本靠数学的题目(然而我考试的时候只有25分)
读清题目后发现就是凑数嘛,....
对啊,就是凑数,怎么凑是重点啊..
于是就绝望了一小时手动枚举n从1到5的情况
吐槽完毕,开始分析:
1.大的数只能由小的数凑出(好像是废话,但确实有用)
2.最小的数必须选
3.一个数的倍数也能凑出
4.一个数减去需要的数能被凑出的话这个数肯定能凑出(比如你有2,3,那么5-3=2,如果2可以凑出那么5也可以凑出)
5.除此以外在没有可以凑出的数
交代码
#include<bits/stdc++.h>
using namespace std;
int a[],o,v[],ans;
int main() {
// freopen("money20.in","r",stdin);
// freopen("1231231.out","w",stdout);
int t;
scanf("%d",&t);
for(int pop=; pop<=t; pop++) {//测t组数据
memset(a,,sizeof a);//初始化
memset(v,,sizeof v);
int n;
scanf("%d",&n);
for(int i=; i<=n; i++)
scanf("%d",&a[i]);
sort(a+,a+n+);//排序,很重要为什么请看刚刚列的第1条
for(int i=; i<=n; i++) {
if(v[a[i]]==)//第一个数或凑不出来的数必须选
ans++;
for(int j=;; j++) {倍数,第3条
o=j*a[i];
if(o<=a[n])//大于最大的数没必要算
v[o]=;
else
break;
}
for(int j=a[i]; j<=a[n]; j++) {
if(v[j-a[i]]==)//减数第4条
v[j]=;
}
}
cout<<ans<<endl;//第5条
ans=;//清空
}
return ;
}