team2012-B2-sol-0024

从 Trac 迁移的文章

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

原文章内容如下：

题意：有一排积木，如果推倒一块，在推倒方向上所有距离小于被推倒积木的都会被推倒，会发生连锁反应，问最少推几块可以推倒全部
思路：先预处理（用单调队列）出每块积木向左向右最多可以推倒几块。F[i]表示前i块推倒的最小代价。计算F[i]时，如果第i块往左推，用RMQ求下能够推倒的范围内的最小值及范围外的最近1块更新下即可。如果第i块是被左边的向右推倒的，可以通过线段树维护最小值，在计算左边的方块时在线段树内更新，到i时取出来更新F[i]

题意：有一排积木，如果推倒一块，在推倒方向上所有距离小于被推倒积木的都会被推倒，会发生连锁反应，问最少推几块可以推倒全部

思路：先预处理（用单调队列）出每块积木向左向右最多可以推倒几块。F[i]表示前i块推倒的最小代价。计算F[i]时，如果第i块往左推，用RMQ求下能够推倒的范围内的最小值及范围外的最近1块更新下即可。如果第i块是被左边的向右推倒的，可以通过线段树维护最小值，在计算左边的方块时在线段树内更新，到i时取出来更新F[i]