o
by 281_33_oh_8_004 @ 2018-11-24 17:07:09
@[GaryMr](/space/show?uid=106427) 那你还不如向我这样做呢
```
#include<iostream>
#include<cmath>
#include<cstdio>
#include<string>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int maxn=100+10;
const int INF=2147483647;
const int maxm=25000+10;
int t,n,m;
int a[maxn];
int f[maxn][maxm];
int sum[maxm];
void read(int &x)
{
int f=1;x=0;char s=getchar();
while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
x*=f;
}
void print(int x)
{
if(x<0)
{
putchar('-');
x=-x;
}
if(x>9)
print(x/10);
putchar(x%10+'0');
}
int main()
{
read(t);
for(int i=1;i<=t;i++)
{
memset(sum,0,sizeof(sum));
read(n);
int maxs=-INF;
for(int j=1;j<=n;j++)
read(a[j]);
sort(a+1,a+1+n);
sum[0]=1;
for(int j=a[1];j<=a[n];j++)
sum[j]=sum[j-a[1]];/先求出第一个能构造出什么数
m=1;
for(int j=2;j<=n;j++)
{
if(sum[a[j]]==1)continue;//前面都可以构成这个数，我还要这个数干嘛
else
{
m++;
for(int k=a[j];k<=a[n];k++)
if(!sum[k])sum[k]=sum[k-a[j]];//他与之前的数能构造的数，1为成功，0为失败。
}
}
cout<<m<<endl;
}
return 0;
}
```
by 天南地北 @ 2018-11-24 17:08:52
@[KM鹿MK](/space/show?uid=51800) 谢谢dalao
by gary2005 @ 2018-11-24 20:46:29
@[GaryMr](/space/show?uid=106427) 在下只是六年级的蒟蒻一枚
by 天南地北 @ 2018-11-25 13:28:50