https://www.acmicpc.net/problem/2629
$O(nW+m)$
dp[i][j] = dp[i-1][j-x[i]] | dp[i-1][j] | dp[i-1][j+x[i]]
#include<cstdio>
int n,m,x,dp[31][30001];
int main() {
dp[0][15000] = 1;
scanf("%d", &n);
for (int i = 1; i <= n; i++){
scanf("%d", &x);
for (int j = 0; j < 30001; j++) {
if (j + x < 30001) dp[i][j] |= dp[i-1][j + x];
if (j >= x) dp[i][j] |= dp[i-1][j - x];
dp[i][j] |= dp[i - 1][j];
}
}
for (scanf("%d", &m); m--;) {
scanf("%d", &x);
printf("%c ", "NY"[x < 15001 && dp[n][x + 15000]]);
}
return 0;
}
댓글 없음 :
댓글 쓰기