关于一个问题

学术版

喵仔牛奶 @ 2022-10-15 15:30:43

有 n 个商品，每个商品有价格与价值，每次区间背包。这样最后可以做到什么复杂度？

by CleinCc @ 2022-10-15 15:40:31

@喵仔牛奶分治背包可以做到 O(nV \log n + qV)，V 为背包容量。

by 喵仔牛奶 @ 2022-10-15 15:42:06

@SweetOrangeOvO 是这篇这样的吗？

https://www.luogu.com.cn/blog/ygsldr/solution-p4141

by Neutralized @ 2022-10-15 15:42:37

这个题也是。

by 喵仔牛奶 @ 2022-10-15 15:44:17

@SweetOrangeOvO @Neutralized thx