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$ 的单调递增子序列的个数。
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$ 覆盖的村庄所需的额外费用。
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$ 号木块的最大贡献。
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$ 位置可以获得的最大幸福总和。
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]$ 转移得到。同时还有考虑从前一天直接转移的状态。
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$ 件玩具的前缀和。首先考虑一般转移方程。
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$ 优，可得：
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]$ 的平均值。
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$ 位置建设了仓库的最小代价。
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$ 可得：
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]$ 后，剩余斜率优化过程与上面两题相同。