线性 dp 复习
这两天复习线性DP……其实不是很想发出来因为感觉同机房的大佬AK这些题单应该都是一两个小时的事……
然后我做两道题看一集番成功地两天才刷完线性DP专题……
T1 导弹拦截
模板题, 复习一下单调队列吧.
但是注意到了一个之前没有认真关注的 $Dilworth$定理:
对偏序集<$A$, $\le$>, 设A中最长链的长度是$n$, 则将A中元素分成不相交的反链, 反链个数至少是$n$.
T2 最长公共子序列
LIS模板
T3 尼克的任务
也是一道简单的二维$(k^2)$DP题, 根据不同的工作进行递推:
$f_i = max(f_i, f_j + job_i.first - job_j.second - 1)$
但是不同工作间的转移边界值得注意.
不是很明白题解中大多数人为何要选择$n*k$的倒序做法……或许有哪位大佬可以讲解一下优越性……
T4 大师
为数不多的一道蓝题, 但是不难发现题目的难度判定有误
$f_{i,j}$表示以$i$结尾, 上一项为$j$的数列, 不难想到$n^3$做法:
$\forall j\lt i, f_{i,j}=\Sigma_{k<j}^{h_i-h_j=h_j-h_k} f_{j,k}+1$
观察到$h\le 2\times 10^4$, 容易想到$n^2$优化, $f_{i,j}$表示以$i$为结尾, 公差为$j$的数列, 则:
$f_{i,j}=\Sigma_{k<i}^{h_i-h_k=j}f_{j,k}$
值得注意的是项数为1或2, 或公差为0的情况.
因为公差正负号与范围问题卡了一次70.
T5 摆花
不是很值得讲的$n^3$暴力DP.
容易想到根据花的种类与数量进行完全背包.
T6 木棍加工
第一眼看以为是二维偏序.
模拟一下样例即可发现与导弹拦截Q2是相同的.
希望各位大佬直接跳到T7.5
是线性DP专题里面值得思考的一题
动态转移方程不难发现, 以$f_{i,j}$表示到第$i$种食材, 占用了$w$的空间, 则:
$f_{i,j}=max{f_{i-1,k}+a_i \times j},k\in [j-1,j+s-1]$
问题是如何优化这个$O(n^3)$的DP
不难发现, $f_{i,j}=max{i-1,k}+a_i \times j$, 则可以选用$O(n^2\log^2 n)$的最值树状数组与常数巨大的$O(n^2\log n)$的线段树, TLE
但是由于若$f_{i-1,j}\ge f_{i-1,k}$且$j<k$, 那么前者无论如何都比后者更优.
因此在长度为$w$的单调队列进行优化即可.
T7.5 看错题的「SWTR-03」Golden Sword
这题是我最开始把T7的题目看错了, 但是不妨进行思考:
若将T7题面中的
宝剑的耐久度为所有原料的耐久度之和.
更改为
宝剑的耐久度为所有被加入炼金锅中的原料的耐久度之和.
又应该如何处理这道题目？
然后我貌似一时没有什么好的思路 但我想赶紧水完……不妨留给偶然点入的浏览者思考.
最后推一下春物3, 看雪乃接受的时候貌似有一种接受自己的错觉
私はぃつまでも雪ノ下雪乃を好きです