RainAir
My OI Blog
RainAir
「NOI2005」瑰丽华尔兹

题目链接

题目大意

现在有一个 $n\times m$ 的矩阵,给定的起始点上有个钢琴,矩阵上有些方格是障碍物,用连续的区间 $[l,r]$ 和一个参数 $d$ 表示在时间 $[l,r]$ 时会向 $d$ 方向滑动(上下左右),当然每个时间点可以选择让钢琴不动,不允许钢琴超出边界或者碰到障碍,询问钢琴可能走的最远距离是多少。
其中 $1 \leq n,m \leq 200$,区间个数 $k \leq 200$,区间最大的右端点 $ T \leq 40000$

题解

首先对于这个题目我们有一个很朴素的暴力,也就是记 $f_{i,x,y}$ 表示在时间点 $i$ 时自己在 $(x,y)$ 能走到的最远距离,转移只需要考虑这个时间点是否让钢琴不动:
$$f_{i,x,y} = min \{f_{i-1,x,y},f_{i-1,x’,y’}+1\}$$
这里和下文中的 $x’,y’$ 都默认是这个点能从哪里到来的位置。
显然这样的 dp 复杂度是 $O(Tn^2)$ 的,时间复杂度和空间复杂度都接受不了。
我们发现这个题目或许想让我们的复杂度与 $k$ 有关,于是我们可以考虑设 $f_{i,x,y}$ 表示在第 $i$ 个时间区间的时候,位置在 $(x,y)$ 能走的路径最大值。
不难发现这一段区间的决策可以拆成一段静止和一段不静止,所以我们可以得到转移方程:
$$f_{i,x,y} = min \{f_{i-1,x,y},f_{i-1,x’,y’}+dis\}$$
这里 $dis$ 为点 $(x,y)$ 到点 $(x’,y’)$ 的曼哈顿距离,下文同理。
注意到这里可能的 $(x’,y’)$ 对最多有 $n$ 个,所以总复杂度为 $O(n^3k)$,需要考虑如何继续优化。
首先这个也可以滚动数组,于是我们设 $g = f_{i-1}$。式子可以重写成
$$f_{x,y} = min\{g_{x’,y’}+dis\}$$
注意到每一段时间区间钢琴都是沿着水平线滑动的,也就是 $x$ 和 $y$ 至多改变一个。我们设这段区间转移时变化的维度是 $x$,忽略不变的那一维可以得到:
$$f_{x} = min\{g_{x+k}+|k|\}$$
这个式子在由 $f_x \to f_{x+1}$ 的过程中具有单调性,所以我们可以使用单调队列维护这一转移,时间复杂度变为 $O(n^2k)$,可以通过该题。

代码

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/633
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 NOIP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

「NOI2005」瑰丽华尔兹
题目链接 题目大意 现在有一个 $n\times m$ 的矩阵,给定的起始点上有个钢琴,矩阵上有些方格是障碍物,用连续的区间 $[l,r]$ 和一个参数 $d$ 表示在时间 $[l,r]$ 时会向 $d$ 方向滑动…
扫描二维码继续阅读
2019-07-07
标签
近期评论