这是本文档旧的修订版！
动态规划 2
二进制优化
题意
给定一个容量为 $m$ 的背包和 $n$ 种物品。每种物品价值为 $v_i$，重量为 $w_i$，数量为 $c_i$。求最多可以得到的价值。
题解
暴力方法为将每种物品转化为 $c_i$ 个独立物品考虑，然后就是一个 $01$ 背包问题。
不难发现任意一个不超过 $c_i$ 的正整数一定用 $1,2,4\cdots 2^n,(c_i-2^{n+1}+1)$ 表示。
于是可以将每种物品拆成 $1,2,4\cdots 2^n,(c_i-2^{n+1}+1)$ 个物品构成的包考虑。
物品总数优化为 $O\left(\sum_{i=1}^n \log {c_i}\right)$，总时间复杂度为 $O\left(m\sum_{i=1}^n \log {c_i}\right)$。
单调队列优化
习题一
题意
一个城镇有 $n$ 个区域，从左到右 $1$ 编号为 $n$，每个区域之间距离 $1$ 个单位距离。
节日中有 $m$ 个烟火要放，给定放的地点 $a_i$，时间 $t_i$。如果你当时在区域 $x$，那么你可以获得 $b_i-\vert a_i-x\vert$ 的开心值。
你每个单位时间可以移动不超过 $d$ 个单位距离。你的初始位置是任意的(初始时刻为 $1$)，求你通过移动能获取到的最大的开心值。
题意
设 $\text{dp}(i,j)$ 表示在 $t_i$ 时刻处于位置 $j$ 能得到的最大快乐值。于是有
$$ \text{dp}(i,j)=\max_{j-d(t_i-t_{i-1})\le k\le j+d(t_i-t_{i-1})}\text{dp}(i-1,k)+b_i-\vert a_i-j\vert $$
单调队列维护即可。时间复杂度 $O(nm)$。
习题二
题意
给定一个容量为 $m$ 的背包和 $n$ 种物品。每种物品价值为 $v_i$，重量为 $w_i$，数量为 $c_i$。求最多可以得到的价值。
题解
考虑滚动背包，有 $\text{dp}_i=\max_{k\le c}(\text{dp}_{i-kw}+kv)$。设 $i=jw+r$，有
$$ \text{dp}_{jw+r}=\max_{k\le c}(\text{dp}_{jw+r-kw}+kv)=\max_{k\le c}(\text{dp}_{(j-k)w+r}-(j-k)v)+jv $$
枚举余数 $r$，对每个余数 $r$，维护 $\text{dp}_{aw+r}-av$ 的单调队列即可。时间复杂度 $O(nm)$。
习题三
题意
给定一个 $n\times m$ 的图，图中有若干障碍物。接下来给定一个物体的初始位置和 $k$ 个时间段。
每个时间段内物体将按每个单位时间一格的速率向给定方向运动。
每个单位时间都可以选择让物体在该单位时间停止运动。问在物体移动过程中不超出图的边界同时不撞上障碍物的前提下物体可以运动的最大路程。
题解
设 $\text{dp}(i,x,y)$ 表示物体在前 $i$ 个时间段最终运动到 $(x,y)$ 能运动的最大路程。以向 $x$ 增大的方向运动为例，有状态转移方程
$$ \text{dp}(i,x,y)=\max_{x-dt\le j\le x}(\text{dp}(i-1,j,y)+x-j)=\max_{x-dt\le j\le x}(\text{dp}(i-1,j,y)-j)+x $$
其中 $dt$ 表示该时间段的长度。发现可以单调队列维护，总时间复杂度 $O(nmk)$。
斜率优化
习题一
题意
给定序列 $c$ 和常数 $L$。已知一个区间 $[l,r]$ 的权值为 $(\sum_{i=l}^r c_i+r-l+1-L)^2$。现要求将 $[1,n]$ 划分为若干连续区间，使得权值和最小。
题解
设 $\text{dp}_i$ 表示区间 $[1,i]$ 的最小答案，设 $s_n=\sum_{i=1}^n a_n$，可以得到状态转移方程
$$ \text{dp}_i=\max(dp_j+(s_i+i-s_j-j-L-1)^2) $$
考虑将变量 $i,j$ 分离，设 $a_i=s_i+i,b_i=s_i+i+L+1$，有
$$ \text{dp}_i=\text{dp}_j+(a_i-b_j)^2=a_i^2+\text{dp}_j+b_j^2+2a_ib_j $$
设 $y=\text{dp}_j+b_j^2,x=2b_j$，于是有
$$ \text{dp}_i-a_i^2=y=a_ix $$
于是维护凸包即可，另外发现 $a_i$ 和 $x$ 递增，于是可以单调队列维护凸包，时间复杂度 $O(n)$。注意最开始需加入 $(a_0,b_0)$。
