这题能用记忆化搜索吗?
查看原帖
这题能用记忆化搜索吗?
494699
卷王慢即快楼主2023/2/23 20:53

我认为好像可以,但是 3939 分,有人帮我调吗?

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, V;
ll ans = 0;
int a[10007];
ll f[10007][50];
inline int dfs(int x, int sum) {
	if(f[x][sum]) return f[x][sum];
	int ans = 0;
	if(sum == V) return f[x][sum] = 1;
	if(x > n) return f[x][sum] = 0;
	if(sum > V) return f[x][sum] = 0;
	for(int i = x; i <= n; i++)
		ans += dfs(i, sum + a[i]);
	return f[x][sum] = ans;
}
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;
}
int 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;
}
2023/2/23 20:53
加载中...