二维
#include <bits/stdc++.h>
using namespace std;
const int N = 1e2 + 10, M = 25010;
int n, m;
int v[N];
int f[N][M]; // f[i][j]:考虑前 i 个物品 总和恰好为 j 的方案数
int main() {
int T; scanf("%d", &T);
while (T--) {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &v[i]), m = max(m, v[i]);
memset(f, 0, sizeof(f));
f[0][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= m; j++) {
f[i][j] = f[i - 1][j];
if (j >= v[i]) f[i][j] += f[i][j - v[i]];
}
}
// 答案就是所有只能被自己凑出来的数的个数 即方案数为 1 的数的个数
int res = 0;
for (int i = 1; i <= n; i++)
if (f[n][v[i]] == 1) res++;
printf("%d\n", res);
}
return 0;
}
一维
#include <bits/stdc++.h>
using namespace std;
const int N = 1e2 + 10, M = 25010;
int n, m;
int v[N];
int f[M]; // f[i][j]:考虑前 i 个物品 总和恰好为 j 的方案数
int main() {
int T; scanf("%d", &T);
while (T--) {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &v[i]), m = max(m, v[i]);
memset(f, 0, sizeof(f));
f[0] = 1;
for (int i = 1; i <= n; i++)
for (int j = v[i]; j <= m; j++)
f[j] += f[j - v[i]];
// 答案就是所有只能被自己凑出来的数的个数 即方案数为 1 的数的个数
int res = 0;
for (int i = 1; i <= n; i++)
if (f[v[i]] == 1) res++;
printf("%d\n", res);
}
return 0;
}