线性 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 「SWTR-03」Golden Sword

希望各位大佬直接跳到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,看雪乃接受的时候貌似有一种接受自己的错觉

私はぃつまでも雪ノ下雪乃を好きです




Enjoy Reading This Article?

Here are some more articles you might like to read next:

  • 「题解 P2282」HNOI2003 历史年份
  • 「题解 P7098」yLOI2020 凉凉
  • 「题解 P5072」Ynoi2015 盼君勿忘
  • 「题解 P7099」yLOI2020 灼
  • 实现一个 std::vector