关于（接近）线性空间/时间复杂度背包

学术版

Shunpower @ 2022-06-11 12:54:19

RT，在写一个题发现需要一些科技。

目前的情况是我有 n 个二元组 (x,y)，取一个二元组需要付出 x 的代价，但可以得到 y 的贡献。我最多付出 n 的代价，如何使得 y 最大。每个二元组只能拿一次（所以不能用疯狂的采药那道题弄）。

显然这是一个 01 背包，然而我只会空间复杂度和时间复杂度都到 $n^2$ 的做法，想问一下，对于这个题特殊的 $x$，能否有空间复杂度**或者**时间复杂度可以达到（接近于）线性的方法？

by Shunpower @ 2022-06-11 12:58:19

@fjy666

能否详尽一点？我不太理解怎么直接 01 背包。

甩个链接也行。

by WYXkk @ 2022-06-11 13:02:03

@Zealous_YH 枚举取几个代价为 2 的

by 王熙文 @ 2022-06-11 13:02:53

https://www.luogu.com.cn/problem/CF3B

by Shunpower @ 2022-06-11 13:03:00

@WYXkk

emm，噢明白了，thx

by Shunpower @ 2022-06-11 13:03:22

@王熙文

草，谢谢

|