看到zhiyangfan讲knapsack怎么O(nv)，这里v是每个物品的大小而不是总大小，想起来我听wls讲过但是我也不会，于是回去看了一眼怎么做放在这里。

· · 个人记录

我们要求 \leq c 的最大的解。

先贪一下得到一个很大的答案 t，那么 c-t<v。于是把选过的取负，问题变成 \leq c-t 的最大的解，这就非常好对吧。

我们希望把过程中所有数的值都控制在 O(v) 范围内。一个想法是轮流取正数和负数，这个想法看起来非常对对吧，但是直接做是 O(n^2v) 的。

维度交换，设 dp(i,k) 表示考虑前 i 个正数，要凑出 k，至少要取到第几个负数，正确性，因为我们是依次考虑，显然取的越少转移越自由，这样状态数是对的了。转移考虑选不选下一个正数，或者枚举下一个选的负数，还是 O(n^2v) 啊。

这里显然有单调性 dp(i,k)\leq dp(i-1,k)。注意到 dp(i-1,k) 已经做过的转移 dp(i,k) 不需要再做，也就是说下一个选的负数只需要在 [dp(i,k),dp(i-1,k)) 中枚举，这样复杂度就是 O(n(n+v)) 了。这谁想的到啊？

wls 讲的时候认为需要把数按绝对值从大到小排序，我不是很理解为什么。

这好像是个xx open cup题，等qoj活了来补个link。

让我们看看BalticOI 22 D1 Uplifting Excursion吧!这个题好像不太能维度交换，贪心之后直接做就过了啊。