网站的域名在哪里看b站24小时自助下单平台网站

题意

出门下转https://agc020.contest.atcoder.jp/tasks/agc020_c

题解

bitset优化dp能否取到某个数

然后从 $(sum+1)/2$ （注意：不是 $sum/2$）往前看看第一个能取到的是啥就好了

调试记录

• 写了 $sum/2$ 导致有重复的数的时候错误

代码

#include <bits/stdc++.h>
using namespace std;bitset<2000*2000+1> S;int main() {int n; scanf("%d", &n);int sum = 0;S[0] = 1;for (int i=1; i<=n; i++) {int x; scanf("%d", &x);S = S | (S << x); sum += x;}// sum /= 2;sum = (sum + 1) / 2;while (!S[sum]) ++sum;printf("%d\n", sum);return 0;
}