2021 暑假训练 dp 优化题解

AC Codes

A – GTY’s birthday gift

矩阵优化 dp

给出序列 $a$ ，每次从序列选两个数相加后，将新数加入序列 $a$ 问操作 $k$ 次后序列的和最大为多少

序列和最大，每次选当前最大和次大相加， $dp [i]=d [i-1]+dp [i-2]$ ，由于 $k$ 范围大，无法直接模拟。考虑到操作方式类似斐波那契数列求合，使用矩阵快速幂优化 $dp$ 。注意模数和多组输入。

B – The Battle of Chibi

树状数组优化 dp

给出长度为 $n$ 的序列，问这个序列中有多少个长度为 $m$ 的单调递增子序列

$dp [i][j]$ ，表示到第 $i$ 个数字，长度为 $j$ 的单调递增子序列的个数。

\begin{aligned} dp[i][j]=\sum_{k\lt i,a[k]\lt a[i]} dp[k][j-1] \end{aligned}

如果单纯枚举转移，不可行。考虑到转移条件的限制，可以将 $a [i]$ 离散化后，使用树状数组计算所以满足条件的状态和。

C – base 基站选址

线段树优化 dp

给出 $n$ 个村庄的横坐标 $D_i$ 。要求在这 $n$ 个村庄内最多选择 $m$ 个作为通讯基站，在村庄 $i$ 建造通讯基站的代价为 $C_i$ 。对于村庄 $i$ ，如果其左右距离超过 $S_i$ 都没有通讯基站，那么需要额外的 $W_i$ 的代价。求最小代价。

$dp [i][j]$ ，表示在第 $i$ 个村庄，修建第 $j$ 个基站的最小费用。 $cost_{k,i}$ 表示第 $k~i$ 个村庄之间没有被基站 $k,i$ 覆盖的村庄所需的额外费用。

\begin{aligned} dp[i][j]=\min_{k\lt i} dp[k][j-1]+cost_{k,i}+c[i] \end{aligned}

首先考虑如何求出 $cost_{k,i}$ 。对于第 $i$ 个村庄，可以二分处理出它所能被覆盖的左右边界为 $l_i$ , $r_i$ 。从 $i$ 推到 $i+1$ 时，对于所有 $r_k=i$ 的村庄若从村庄 $1∼l_k−1$ 转移过来则必定要赔偿村庄 $k$ 的费用，然后可以用线段树维护区间最小值，从而找到转移位置。

D – Fence

单调队列优化 dp

给出 $n$ 个木块， $k$ 个人。每个人有三个参数 $l , p , s$ , 分别表示每个人最多加工的木块数，每个人加工一个木块的贡献，每个人加工木块区间必须包含的木块编号，求最大贡献和。

$dp [i][j]$ ，表示第 $i$ 个人加工到 $j$ 号木块的最大贡献。

\begin{aligned} dp[i][j]&=\max(dp[i-1][j],dp[i][j-1])\\ dp[i][j]&=\max_{k\lt i,k\lt s[i],j-k\leq l[i]} dp[i-1][k]+p[i]\times(j-k) \end{aligned}

然后我们发现转移是选 $dp [i-1][k]+p [i]\times (j-k)$ 最大的进行转移，然后我们可以维护一个递减的单调队列，放当前的值，和位置下标。转移的时候弹出不合法的元素，然后直接取队首进行转移即可。

E – Watching Fireworks is Fun

单调队列优化 dp

主要街道有 $n$ 个区域，从左到右编号为 $1~n$ , 每个相邻部分之间的距离为 $1$ 。在节日期间，将推出烟花爆竹。第 $i$ 次发射是在 $a_i$ 部分，发射时间为 $t_i$ 。如果你在第 $i$ 次发射时在 $x$ 处，将获得幸福值 $b_i-| a_i – x |$ 。在单位时间间隔内移动最多 $d$ 个单位，但禁止走出主要街道。此外，可以在初始时刻（时间等于 1）处于任意区域，并希望最大化从观看烟花中获得的幸福总和。

$dp [i][j]$ 表示到放第 $i$ 个烟花的时候站在 $j$ 位置可以获得的最大幸福总和。

\begin{aligned} dp[i][j]&=\max_{j-d\times t\leq k,k\leq j+d\times t} dp[i-1][k]+b[i]-|a[i]-j| \end{aligned}

首先烟花要先按照燃放时间排序，对于 $dp [i][j]$ ， $k$ 的取值范围的长度是固定的，所以可以考虑使用单调队列来维护上一状态的取值，保证转移时取到最大值。

F – Water Balance

单调栈优化 dp

给你 $n$ 个数的序列 $a$ 。每次操作选择一个区间 $[l,r]$ ，把这个区间的数都改为这个区间的平均数。你可以进行任意次操作，使得这个序列的字典序最小。

为使序列的字典序最小，序列中的数一定单调递增。进行区间选择合并时，一定会使之前的区间平均值下降。所以可以使用单调栈来维护区间的合并，合并后区间的权值为平均值。

G – 股票交易

单调队列优化 dp

$dp [i][j]$ 表示第 $i$ 天拥有 $j$ 张股票可以赚到的最多钱数。考虑到两次交易直接需要间隔 $w$ 天，所以 $dp [i][j]$ 可以从 $dp [i-w-1][k]$ 转移得到。同时还有考虑从前一天直接转移的状态。

\begin{aligned} dp[i][j]&=\max(dp[i][j],dp[i-1][j])\\ dp[i][j]&=\max_{k\leq as[i]} dp[i-w-1][j-k]-k\times ap[i]\\ dp[i][j]&=\max_{k\leq bs[i]} dp[i-w-1][j+k]+k\times bp[i] \end{aligned}

由于转移区间有明显的上下边界，可以考虑用单调队列来维护区间最值。

H – 瑰丽华尔兹

单调队列优化 dp

$dp [i][j]$ 表示在每次移动后落在 $[i,j]$ 位置的最大答案。每次移动答案只会从一个方向上转移，同时转移的长度有限制。转移过程和上一题类似，主要是需要考虑四个方向的转移，同时在遇到无法通过的点时需要清空队列。

I – 玩具装箱 toy

斜率优化 dp

$dp [i]$ 表示前 $i$ 件玩具的最小费用， $sum [i]$ 表示前 $i$ 件玩具的前缀和。首先考虑一般转移方程。

\begin{aligned} dp[i]=\min(dp[j]+(sum[i]+i−sum[j]−j−L−1)^2) \end{aligned}

如果直接进行转移时间复杂度为 $O (n^2)$ ，肯定无法解决。

令 $a [i]=sum [i]+i，b [i]=sum [i]+i+L+1$ 。

$dp[i]=dp[j]+(a[i]-b[j])^2$

展开后：

$dp[i]=dp[j]+a[i]^2−2\times a[i]\times b[j]+b[j]^2$

移项可得：

$2\times a[i]\times b[j]+dp[i]−a[i]^2=dp[j]+b[j]^2$

将 $b [j]$ 看作 $x$ ， $dp [j]+b [j]^2$ 看作 $y$ 可得：

$2\times a[i]\times x+dp[i]−a[i]^2=y$

这个式子就可以看作一条斜率为 $2a [i]$ 的直线，由于 $a [i]$ 为固定值。

对于 $i$ 的两个可转移状态 $j_1,j_2$ ，如果 $j_2$ 比 $j_1$ 优，可得：

\begin{aligned} y[j_1]-2a[i]x[j_1]&\geq y[j_2]-2a[i]x[j_2]\\ 2a[i]&\geq \frac{y[j_2]-y[j_1]}{x[j_2]-x[j_1]} \end{aligned}

所以对于当前的后续状况，只需要考虑斜率，保证斜率最优的情况，就能确保答案最优。

同样可以使用单调队列来保存候选状态。

J – 征途

斜率优化 dp

设 $x [i]$ 表示第 $i$ 天走的路程， $x_0$ 为 $x [i]$ 的平均值。

\begin{aligned} s^2&=\frac{\sum (x[i]-x_0)^2}{m}\\ s^2&=\frac{\sum x[i]^2+x_0^2-2x[i]x_0}{m}\\ s^2&=\frac{\sum x[i]^2}{m}-x_0^2\\ m^2s^2&=m\sum x[i]^2-m^2x_0^2 \end{aligned}

由于 $x_0$ 是一个定值，题目本质就转换为求 $\sum x [i]^2$ 的最小值。

状态转移公式和上一题类似，只不过多了分段此时的限制，所以状态转移需要做 $m$ 次。

K – 仓库建设

斜率优化 dp

设 $dp [i]$ 表示在 $i$ 位置建设了仓库的最小代价。

\begin{aligned} sump[i]&=\sum_{j\leq i}p[i]\\ sum[i]&=\sum_{j\leq i}p[i]\times x[i]\\ dp[i]&=\min_{j\lt i}dp[j]+x[i]\times (sump[i]-sump[j])-sum[i]+sum[j]+c[i] \end{aligned}

对于两个转移状态 $j_1,j_2$ ，如果 $j_2$ 优与 $j_1$ 可得：

\begin{aligned} dp[j_2]-x[i]\times sump[j_2]+sum[j_2]&\lt dp[j_1]-x[i]\times sump[j_1]+sum[j_1]\\ dp[j_2]+sum[j_2]-dp[j_1]-sum[j_1]&\lt x[i]\times (sump[j_2]+sump[j_1])\\ \frac{dp[j_2]+sum[j_2]-dp[j_1]-sum[j_1]}{sump[j_2]+sump[j_1]}&\lt x[i] \end{aligned}

将 $dp [j]+sum [j]$ 看作 $y [j]$ ， $sump [j]$ 看作 $x [j]$ 后，剩余斜率优化过程与上面两题相同。