Zirnc's Blog
Recent content on Zirnc's Blog
马上订阅 Zirnc's Blog RSS 更新: https://blog.chungzh.cn/index.xml
Luogu-P2254 「NOI2005」瑰丽华尔兹
题意
不妨认为舞厅是一个 $N$ 行 $M$ 列的矩阵，矩阵中的某些方格上堆放了一些家具，其他的则是空地。钢琴可以在空地上滑动，但不能撞上家具或滑出舞厅，否则会损坏钢琴和家具，引来难缠的船长。每个时刻，钢琴都会随着船体倾斜的方向向相邻的方格滑动一格，相邻的方格可以是向东、向西、向南或向北的。而艾米丽可以选择施魔法或不施魔法：如果不施魔法，则钢琴会滑动；如果施魔法，则钢琴会原地不动。
艾米丽是个天使，她知道每段时间的船体的倾斜情况。她想使钢琴在舞厅里滑行的路程尽量长，这样 1900 会非常高兴，同时也有利于治疗托尼的晕船。但艾米丽还太小，不会算，所以希望你能帮助她。
$100%$ 的数据中，$1\leq N, M \leq 200$，$K \leq 200$，$T\leq 40000$。
分析
首先我们定义一下状态。设 $dp[t][i][j]$ 表示 t 时刻，在 $(i, j)$ 滑行的最长路程长度。状态转移方程是 $dp[t][i][j] = \max(dp[t-1][i][j], dp[t-1][i^{’}][j^{’}])$，$i^{’}$ 和 $j^{’}$ 是合法的走过来的位置，取决于 $t$ 时刻船体倾斜的方向。
这样设计状态的话，时间复杂度为 $O(TNM)$，空间似乎也是问题。
这时候我们发现还有一个变量 $K$ 没有用到，考虑把状态设为 $dp[t][i][j]$ 表示在第 $t$ 时间段内，在 $(i, j)$ 滑行的最长路程长度。时间复杂度为 $O(KN^3)$，暂时还不行。
我们看看能不能进一步优化。下面假设当前船体倾斜的方向是东。设当前时间段长度是 $tim$，上一个时间段钢琴的位置在 $(i, m)$，那么 $dp[t][i][j] = \max_{j-m<=tim}{dp[t-1][i][m]+j-m}$。在这个式子中，只有 $m$ 一个变量，并且 $j-m<=tim$，合法决策在一段相邻区间内，可以用到单调队列优化！
对于两个决策 $m_1 < m_2$，$m_2$ 优于 $m_1$ 时仅当：
$$ \begin{aligned} dp[t-1][i][m_1]+(j-m_1) & < dp[t-1][i][m_2]+(j-m_2) \\ dp[t-1][i][m+1]+m_2-m_1 & < dp[t-1][i][m_2] \end{aligned} $$
在单调队列向尾部加入新决策时，我们就用这个公式来判断队尾需不需要出队，维护单调性。
这样时间复杂度降到了 $KN^2$。
注意细节：
- 不合法（$-1$）的决策不要入队
|