01背包枚举状态,bitset优化时间复杂度
int n,k; cin >> n >> k; bitset<100010>dp; dp[0] = 1; for(int i=0;i<n;i++){ int x; cin >> x; dp|=(dp<<x); } int ans = 0; for(int i=0;i<=k;i++){ if(!dp[i]){ ans ++; dp|=(dp<<i); } } cout << ans<< endl;
注册一个 三鼎OJ 通用账户,您就可以在我们提供的所有在线评测服务上提交代码、参与讨论。
使用您的 三鼎OJ 通用账户