zrj2012-B3-0024

从 Trac 迁移的文章

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

原文章内容如下：

题目大意：给出N个多米诺骨牌，每个骨牌有一个横坐标位置xi与高度hi。

你可以随意选取某个骨牌推到它，如果倒下的骨牌i与另一个骨牌j满足(|xi-xj|<=hi，且xi<=xj（往右推）或xi>=xj（往左推）），并且j之前没有倒下，那么j会向i倒下的方向倒下。

问你最少推几个骨牌可以让N个骨牌都倒下。PS：骨牌可以进行连锁反应式倒下。

先将骨牌按横坐标排序。

首先，我们需要预处理出第i个骨牌向左（右）倒最远可以推到的骨牌left[i]（right[i]）。这里可以使用单调队列来处理，我们以求向左推为例。

用a[i]来存放单调队列，满足x[a[i]]<x[a[i+1]]-h[a[i+1]], x[a[i]]<x[a[i+1]]且left[a[i]]<left[a[i+1]]（事实上这里应该也有a[i]=left[a[i+1]]-1，因为队列存放的覆盖必然是没有重叠也没有空缺的），m是队列的长度。

接下来我们处理地i个骨牌，首先令left[i]=i。如果x[i]-h[i]<=x[a[m]]，即第i个骨牌能够碰倒第m个骨牌，那么令left[i]==left[a[m]]。同时，我们知道向左推第i个与第a[m]个骨牌，最远到达的位置是一样地，但是x[i]>x[a[m]]，因此对于之后的骨牌，如果它能够碰倒i，就不用去查询a[m]了，如果不能碰倒i，它也不可能碰倒a[m]。因此我们把a[m]踢出队列，继续查询当前的队尾，直到m=0或x[i]-h[i]>x[a[m]]。最后，我们把i加入队列。

因为每个点入队一次，且至多出队一次，一旦查询成功必然出队，因此复杂度是o(n)的。

接下来就是要考虑整个骨牌的问题。我们令f[i]表示前i个骨牌都已经倒下时的最少要推到几个骨牌。

然后我们从左往右计算，对于骨牌i，我们要分两种情况讨论：

 * 1、向左推：f[i]的状态必然是由f[left[i]-1]~f[i-1]中最小的那个转移过来。这里如何使用单调队列我没想到，因此是用线段是来维护。

 * 2、向右推：我们直接用f[i-1]+1去更新f[right[i]]（即前i个已经倒下，现在第i个向右倒的情况）即可。为什么只需要更新到f[right[i]]而无视了i+1~right[i-1]呢？

               我们可以这样考虑。对于i<k<right[i]，如果我们用f[i-1]+1去更新了f[k]，它可以去更新什么呢？

               * 如果我们把k+1往右推，明显k+1<=right[i]，right[k+1]<=right[i]，无论k+1去更新哪个点，都没有直接用i去更新来得优。

               * 如果我们把某个p>k往左推，满足k>=left[p]-1，想用f[k]更新f[p]。但是f[k]是由i向右倒得到的，如果p>right[i]，我们可以从f[right[i]]处得到答案。如果p<=right[i]，f[k]+1>f[i]，我们选择把i往右推可以得到一样甚至更好的效果，花费却比用k更新少。

              因此，我们发现，对于i<k<right[i]，我们没有必要其更新它。

最后的答案就是f[n]。

题目大意：给出N个多米诺骨牌，每个骨牌有一个横坐标位置xi与高度hi。

你可以随意选取某个骨牌推到它，如果倒下的骨牌i与另一个骨牌j满足(|xi-xj|<=hi，且xi<=xj（往右推）或xi>=xj（往左推）），并且j之前没有倒下，那么j会向i倒下的方向倒下。

问你最少推几个骨牌可以让N个骨牌都倒下。PS：骨牌可以进行连锁反应式倒下。

先将骨牌按横坐标排序。

首先，我们需要预处理出第i个骨牌向左（右）倒最远可以推到的骨牌left[i]（right[i]）。这里可以使用单调队列来处理，我们以求向左推为例。

用a[i]来存放单调队列，满足x[a[i]]

接下来我们处理地i个骨牌，首先令left[i]=i。如果x[i]-h[i]<=x[a[m]]，即第i个骨牌能够碰倒第m个骨牌，那么令left[i]==left[a[m]]。同时，我们知道向左推第i个与第a[m]个骨牌，最远到达的位置是一样地，但是x[i]>x[a[m]]，因此对于之后的骨牌，如果它能够碰倒i，就不用去查询a[m]了，如果不能碰倒i，它也不可能碰倒a[m]。因此我们把a[m]踢出队列，继续查询当前的队尾，直到m=0或x[i]-h[i]>x[a[m]]。最后，我们把i加入队列。

因为每个点入队一次，且至多出队一次，一旦查询成功必然出队，因此复杂度是o(n)的。

接下来就是要考虑整个骨牌的问题。我们令f[i]表示前i个骨牌都已经倒下时的最少要推到几个骨牌。

然后我们从左往右计算，对于骨牌i，我们要分两种情况讨论：

• 1、向左推：f[i]的状态必然是由f[left[i]-1]~f[i-1]中最小的那个转移过来。这里如何使用单调队列我没想到，因此是用线段是来维护。
• 2、向右推：我们直接用f[i-1]+1去更新f[right[i]]（即前i个已经倒下，现在第i个向右倒的情况）即可。为什么只需要更新到f[right[i]]而无视了i+1~right[i-1]呢？

我们可以这样考虑。对于i

* 如果我们把k+1往右推，明显k+1<=right[i]，right[k+1]<=right[i]，无论k+1去更新哪个点，都没有直接用i去更新来得优。

* 如果我们把某个p>k往左推，满足k>=left[p]-1，想用f[k]更新f[p]。但是f[k]是由i向右倒得到的，如果p>right[i]，我们可以从f[right[i]]处得到答案。如果p<=right[i]，f[k]+1>f[i]，我们选择把i往右推可以得到一样甚至更好的效果，花费却比用k更新少。

因此，我们发现，对于i

最后的答案就是f[n]。