DP优化解法同1123小偷的背包，dp数组大一点就过了
#include<cstdio>
#include<cstring>
int main() {
int S, n;
while(scanf("%d%d", &S, &n) != EOF){
int dp[201], w[101];
memset(dp, 0, sizeof(dp)); dp[0] = 1;
for (int i = 1; i <= n; i++) scanf("%d", &w[i]);
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");
}
}
数据里有个142的，所以dp数组至少也要200，在机试的时候，先给足空间！不过希望题目也能给足些条件，因为着实判断不出背包大小。
The road of your choice, you have to go on !
粤ICP备16082171号-1
登录后发布评论
dp数组需要开大一点