1981
可以当作背包来做,但只能选一次所以是分组背包
错误点
在第一次使用2*target + 1
错了以后发现target可以超好几倍,自己大概计算了一下然后又试了几个例如7*target + 1
,最后自暴自弃用最大的所有sum来作为size,然后就超时了。
看了题解发现如果答案不在2*target + 1
那么就是每个row中最小值的和。为什么?
因为要么远小于target
要么远大于, 此外我们没有负数,所以在远大于的情况下,我们只需找到最小的sum即是解。
可以当作背包来做,但只能选一次所以是分组背包
在第一次使用2*target + 1
错了以后发现target可以超好几倍,自己大概计算了一下然后又试了几个例如7*target + 1
,最后自暴自弃用最大的所有sum来作为size,然后就超时了。
看了题解发现如果答案不在2*target + 1
那么就是每个row中最小值的和。为什么?
因为要么远小于target
要么远大于, 此外我们没有负数,所以在远大于的情况下,我们只需找到最小的sum即是解。