关于这题多重背包的复杂度
查看原帖
关于这题多重背包的复杂度
184168
xuanxuan001楼主2020/5/25 19:51

RT,这题询问的钱数达到5×1055 \times 10^5,而多重背包中每个多个数量物品会变成O(logO(\log 数量))个单个物品,在本题中最多有10310^3个,log103=10log 10^3=10,所以最后复杂度是5×105×10×200=1095 \times 10^5 \times 10 \times 200=10^9,就算有的物品跑不满也不可能卡过,那么是我哪里推错了还是它的复杂度有问题?

官方题解链接

2020/5/25 19:51
加载中...