文章

11

粉丝

20

获赞

4

访问

8.3k

头像
DP空间优化O(n),或算法(内存140kb)
P1123 中国科学技术大学机试题
发布于2023年8月5日 13:36
阅读数 625

#include<stdio.h>
int dp[31], w[21];
int main() {
	int S, n;
	scanf("%d%d", &S, &n);
	for (int i = 1; i <= n; i++) scanf("%d", &w[i]);
	dp[0] = 1;
	for (int i = 1; i <= n; i++)
		for (int j = S; j >= w[i]; j--)
			dp[j] |= dp[j - w[i]];

	if (dp[S]) puts("yes!");
	else puts("no!");
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发