Skip to main content

1981

可以当作背包来做,但只能选一次所以是分组背包

错误点

在第一次使用2*target + 1错了以后发现target可以超好几倍,自己大概计算了一下然后又试了几个例如7*target + 1,最后自暴自弃用最大的所有sum来作为size,然后就超时了。

看了题解发现如果答案不在2*target + 1 那么就是每个row中最小值的和。为什么? 因为要么远小于target要么远大于, 此外我们没有负数,所以在远大于的情况下,我们只需找到最小的sum即是解。

提醒自己: 为什么不用bitset

最大值只有4900,使用bitset轻轻松松解决