前情提示:会TLE,吸口氧可以过
先想到:对于一个系统,当且仅当前面的数凑得出来这个数
之后就像一个完全背包了
Code:
#include<algorithm>
#include<bitset>
#include<cctype>
#include<cerrno>
#include<clocale>
#include<cmath>
#include<complex>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<limits>
#include<list>
#include<map>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<utility>
#include<vector>
#include<cwchar>
#include<cwctype>
#include<chrono>
#include<random>
#include<unordered_map>
using namespace std;
#define ll long long
#define ull unsigned long long
#define rll register long long
#define ri register int
//#define int long long
const int N=110;
int T;
int n;
int a[N];
int f[30010];
inline ll read(){
ll x=0,y=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-')
y=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=x*10+c-'0';
c=getchar();
}
return x*y;
}
inline bool cmp(int x,int y){
return x<y;
}
signed main(){
T=read();
//freopen("money.in","r",stdin);
//freopen("money.ans","w",stdout);
while(T--){
int m=0;
memset(a,0,sizeof(a));
memset(f,0,sizeof(f));
n=read();
for(ri i=1;i<=n;i++)
a[i]=read();
sort(a+1,a+n+1,cmp);
for(ri i=1;i<=n;i++){
memset(f,0,sizeof(f));
for(ri j=1;j<i;j++)
for(ri k=a[j];k<=a[i];k++)
f[k]=max(f[k],f[k-a[j]]+a[j]);
if(f[a[i]]!=a[i])
m++;
}
printf("%d\n",m);
}
return 0;
}