杂题选做
#1 CF1566F
题目传送门
我们先去掉初始就被访问的区间;然后套路地,如果一个区间包含了其他区间,那么该区间可以去掉。
然后我们考虑一个点的移动范围:就是它左边的点到它右边的点构成的区间。否则我们完全可以让左边或右边的点去移动。
然后一个点至多换一次方向,不然一定可以转化为只换一次方向且次数更少的方案。特别地,我们将不换方向的运动看成反方向不移动后换一次方向的运动。
于是我们对于相邻的两个点进行 dp,枚举它们之间的两个相邻区间,然后枚举两个点的初始运动方向。转移即可。
#2 P8179
题目传送门
首先,我们注意到:一个轮胎的使用时间是一段连续区间。不然可以把所有区间合并,然后节省换胎时间。
其次,我们考虑 \(t = 0\) 怎么做。此时使用费用是单调递增的,于是我们可以使用栈来维护当前最小代价。
那么 \(t \neq 0\) 呢?我们考虑把 \(t\) 加到第一次使用的代价,然后就发现此时费用并不单调。
但是我们发现取到第 \(\sqrt t+1\) 个时,因为加 \(t\) 导致影响就没了。(因为此时代价不小于第一个,所以能取到说明即使第一个加了 \(t\),这个物品取这么多个还是优的)
因此我们对前 \(\sqrt t\) 次此时做分组背包,对之后的使用用堆来维护。
可以明确的是:我们的选取一定是合法的,因为如果前面背包部分取不到 \(\sqrt t\) 个,那么说明取 \(\sqrt t\) 个不优,取 \(\sqrt t+1\) 个更不优。