@[艾因斯坦](/user/494699) https://www.luogu.com.cn/record/102822645
by ACRUSHj @ 2023-02-23 21:10:05
@[艾因斯坦](/user/494699)
A 了!
~~竟然没有 MLE……~~
```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
int n, V;
ll ans = 0;
int a[20007];
ll f[20007][10007];
inline int dfs(int x, int sum) {
if(f[x][sum]) return f[x][sum]-1;
int ans = 0;
if(sum == V) return (f[x][sum] = 2)-1;
if(x > n) return (f[x][sum] = 1)-1;
if(sum > V) return (f[x][sum] = 1)-1;
for(int i = x; i <= n; i++)
ans += dfs(i, sum + a[i]);
return (f[x][sum] = ans+1)-1;
}
inline int read() {
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9') {
if(ch == '-') f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9') {
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
signed main() {
n = read(), V = read();
for(int i = 1; i <= n; i++)
a[i] = read();
sort(a + 1, a + n + 1);
printf("%lld", dfs(1, 0));
return 0;
}
```
by 035966_L3 @ 2023-02-23 23:08:27
@[wosizmcy](/user/365654) 为什么要 $f_{x,sum} = ans + 1$ 啊?
by 卷王 @ 2023-02-24 20:05:27
@[wosizmcy](/user/365654) 没事了,过了,memset -1 也可以
by 卷王 @ 2023-02-24 20:24:47