题解
由于每个数字只能选一次,那么这道题其实就是一个01背包
初始条件$f[0] = 1$
状态转移方程$f[j] += f[j - a[i]]$
code
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e4 + 100;
template <typename T>
inline void read(T &s) {
s = 0;
T w = 1, ch =getchar();
while (!isdigit(ch)) { if (ch == '-') w = -1; ch = getchar(); }
while (isdigit(ch)) { s = (s << 1) + (s << 3) + (ch ^ 48); ch = getchar(); }
s *= w;
}
int n, m;
int a[maxn], f[maxn];
int main() {
read(n), read(m);
for (int i = 1; i <= n; ++i) {
read(a[i]);
}
memset(f, 0, sizeof(f));
f[0] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = m; j >= a[i]; --j) {
f[j] += f[j - a[i]];
}
}
printf("%d\n", f[m]);
return 0;
}