Luogu

分析

发现简化后的系统显然是原系统的子集。

做一遍可行性DP，删掉所有可以表示出来的数就行。

用bitset重写了一遍，吸个氧直接到了66ms，比以前那个3800+ms的代码不知道高到哪去了。

代码

#include <bits/stdc++.h>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

int n;
int a[110];

inline void solve() {
    n=read();
    for (re int i=1;i<=n;++i) a[i]=read();
    stable_sort(a+1,a+n+1);
    bitset<25010> S;
    S[0]=1; int ans=0;
    for (re int i=1;i<=n;++i) {
        if (S[a[i]]) continue;
        ++ans;
        for (re int j=1;j*a[i]<=a[n];++j)
            S|=(S<<a[i]);
    }
    printf("%d\n",ans);
}

int main() {
    int T=read();
    while (T--) solve();
    return 0;
}