「NOIAC 707」LP 题解

突然在 U 群里爆出了这题，回想起了这道当时自己感觉挺有趣的一题，过来写篇题解。

题目描述

有三个长度为 $n$ 的数列 $\{a_1,a_2,\ldots,a_n\},\{b_1,b_2,\ldots,b_n\},\{c_1,c_2,\ldots,c_n\}$，要满足约束

$\sum_{i=1}^n a_ix_i\le P \\ \sum_{i=1}^n b_ix_i\ge P \\ \forall 1\le i\le n,x_i\in \{0,1\}$

最小化

$w=\sum_{i=1}^n c_ix_i$

数据范围：$n\le 1000$，$P\le 10000$，$\forall 1\le i\le n,0\le a_i\le b_i\le 10000$，$\forall 1\le i\le n,0\le c_i\le 2\times 10^6$。

题解

设 $f(i,j)$ 表示确定了 $x_{1\sim i}$，且满足 $\sum_{k=1}^i a_kx_k\le j,\sum_{k=1}^i b_kx_k\ge j$ 时，$\sum_{k=1}^i c_kx_k$ 的最大值。

则有转移方程：

$f(i,j)=\max\{f(i-1,j),\max\limits_{j-b_i\le k\le j-a_i}\{f(i-1,k)+c_i \}\}$

显然可以用单调队列优化转移，时间复杂度为 $O(nP)$，使用滚动数组可以将空间复杂度优化为 $O(P)$。

关键条件是 $a_i\le b_i$，没这个条件转移不成立。