题目大意

给定长为 的序列 ，设 。现在希望找到一个尽可能短的，设长为 的序列 使得 。求 。

题解

大概可以猜到 是 的子集。那么我们考虑一开始令 为空，然后不断往 中加入 的元素，且维持 尽量小。

那么加入的顺序必然是从小到大。当 中已有元素可以拼出 时就不加入 ，否则加入。“是否能拼出”可以用完全背包求出。

因此总的时间复杂度为 。

#include <bits/stdc++.h>
#define INF 2000000000
#define MOD 1000000007
#define MAXN 200005
#define REP(temp, init_val, end_val) for (int temp = init_val; temp <= end_val; ++temp)
#define REPR(temp, init_val, end_val) for (int temp = init_val; temp >= end_val; --temp)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> intpair;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while (c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while (c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
inline int lowbit(int x){
    return x & (-x);
}
inline int modadd(int x, int y){
    return (x + y >= MOD ? x + y - MOD: x + y);
}
inline int sgn(int x){
    return (x < 0 ? -1: (x > 0 ? 1: 0));
}
template<typename T>
T gcd(T a, T b){
    return (!b) ? a: gcd(b, a % b);
}
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

/*--------------------------------------------------------------------*/
/*--------------------------------------------------------------------*/

int n, a[105], maxi;
bool ok[25005];
void init(){
    n = read();
    REP (i, 1, n){
        a[i] = read();
    }
    memset(ok, 0, sizeof(ok));
    sort(a + 1, a + n + 1);
    maxi = a[n];
}
void solve(){
    ok[0] = true;
    int cnt = 0;
    REP (i, 1, n){
        if (ok[a[i]]) continue;
        ++cnt;
        for (int j = a[i]; j <= maxi; ++j){
            ok[j] = ok[j] || ok[j - a[i]];
        }
    }
    printf("%d\n", cnt);
}
int main(){
    int T = read();
    while (T--){
        init();
        solve();
    }
    return 0;
}