team2012-D1-sol-0024

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

=== 题目大意 ===
有 n 个木块, 每块木块都可以向左推倒或向右推倒. 如果某个木块 x 高度大等于与另一个木块 y 之间的距离, 那么向木块 y 方向推倒就会压倒木块 y. 求最少推倒多少个木块就可以使全部木块都倒掉.

=== 数据范围 ===
 * 1 <= n <= 100000

=== 解题思路 ===
这题目首先想到的就是 DP. 如果只能向左推, 那么就是一个很简单的 DP: 先处理一下每一个木块往左推可以推倒的最左一个木块 L[i]. 然后从左往右做一边 DP 就好了. 加入"向右推"这个决策以后也可以类似地思考: 首先也把每个木块最右可以推倒的木块 R[i] 求出来. dp[i] 表示推倒前 i 个木块最少需要推 dp[i] 次. 然后转移方程就变成下面这样:
 * dp[i] = min(dp[i], min{dp[j-1]|L[i]<=j<=i}+1) // 木块 i 往左推
 * dp[j] = min(dp[j], dp[i-1]+1) (i<=j<=R[i]) // 木块 i 往右推
这里显然是要做一个区间查询和区间修改, 可以用线段树来做. 时间复杂度是 O(n*log(n)).

这题其实可以用单调队列优化, 包括上面求 L[i] 和 R[i] 的时候, 但是我只写了线段树的版本, 后面会学习一下然后再写一遍单调队列的算法.

题目大意

有 n 个木块, 每块木块都可以向左推倒或向右推倒. 如果某个木块 x 高度大等于与另一个木块 y 之间的距离, 那么向木块 y 方向推倒就会压倒木块 y. 求最少推倒多少个木块就可以使全部木块都倒掉.

数据范围

• 1 <= n <= 100000

解题思路

这题目首先想到的就是 DP. 如果只能向左推, 那么就是一个很简单的 DP: 先处理一下每一个木块往左推可以推倒的最左一个木块 L[i]. 然后从左往右做一边 DP 就好了. 加入"向右推"这个决策以后也可以类似地思考: 首先也把每个木块最右可以推倒的木块 R[i] 求出来. dp[i] 表示推倒前 i 个木块最少需要推 dp[i] 次. 然后转移方程就变成下面这样:

• dp[i] = min(dp[i], min{dp[j-1]|L[i]<=j<=i}+1) // 木块 i 往左推
• dp[j] = min(dp[j], dp[i-1]+1) (i<=j<=R[i]) // 木块 i 往右推

这里显然是要做一个区间查询和区间修改, 可以用线段树来做. 时间复杂度是 O(n*log(n)).

这题其实可以用单调队列优化, 包括上面求 L[i] 和 R[i] 的时候, 但是我只写了线段树的版本, 后面会学习一下然后再写一遍单调队列的算法.