team2012-E1-mysol-0024
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
{{{
/* 解题报告 //
给出 n 个木块，每个木块在 X[i] 的位置，高度为 H[i]
你可以将它们以朝左或朝右的方向推倒，会产生连锁反应
问至少要手动推倒多少块，才能完全使所有木块都倒下
首先，题目里的木块可能在相同的 X[i] 处，所以要先去重
对于有相同 X[i] 的木块，只保留 H[i] 最大的一个
然后用两个单调队列 L 和 R 去计算下面两个数组：
1. u[i] = 每个木块往左推倒，最远能碰倒的木块编号
2. v[i] = 每个木块往右推倒，最远能碰倒的木块编号
单调队列里面每个元素都是一个 pair<int, int>
表示在 first 的位置有一个木块，推倒它后最远能碰倒木块编号 second
每次在队列尾部新添加一个木块之前，先将它能碰倒的所有木块弹出队列
在此过程中，可以得到它能碰倒的最远木块编号，然后将它自己加入队列中
前面的预处理部分得到 u[] 和 v[] 数组后，就能用这两个数组进行 dp 了
用 dp[i] 表示弄倒了前 i 个木块所需要最少的手动推倒次数，转移方程是：
1. dp[i] = min(dp[i], min(dp[u[i] - 1] .. dp[i - 1]) + 1)
2. dp[i] .. dp[v[i]] = min(dp[i] .. dp[v[i]], dp[i - 1] + 1)
前一项是用连续的一段元素去更新一个元素
后一项是用一个元素去更新连续的一段元素
显然，这两个 dp 方程可以用线段树进行优化，达到 O(n log n) 的复杂度
不过我的做法是继续使用单调队列，在单调队列 H 中：
位置靠后的元素所需要的推倒次数必须大于靠前的
如果靠后的元素的值更小或相同，则靠前的元素没有存在的意义了
于是此时将靠前的弹出
如果只考虑前一项 dp 转移方程，非常简单，上面其实已经将做法全部写完了
每次添加新元素之前先维护单调队列，然后只要 dp[i] = size(H) + 1 即可
但现在有『可以向右推倒』这个条件的存在，所以需要进一步考虑
仔细观察后一项 dp 转移方程，发现它试图将一个区间的所有 dp 值
统一地改为某个特定的值，并且每次修改不会增加 dp 值，而只会降低
但我们的单调队列，对于相同的 dp 值，只会保留最靠后的一个
因此对于后一项 dp 转移方程，其实只要计算第 v[i] 个元素的值即可
其他元素的更新操作没有意义，因为到以后的某个时刻，那些值总会被弹出队列
所以现在也没必要计算了（重要的贪心优化）
对于每个木块 i，处理完两项 dp 方程后，最后将得到的 dp[i] 加入到队列中
并按上文中的方法去维护单调队列，弹出不必要的元素
我程序里的单调队列都是手工数组实现，主要是为了方便做一些操作
顺便说明一下，程序里名为 **at 的变量都是单调队列的队尾元素下标
// By 猛犸也钻地 @ 2012.07.27 */
}}}
{{{
#include <cstdio>
#include <algorithm>
using namespace std;
typedef pair<int,int> PII;
const int INF = 1000000007;
PII a[100001],L[100001],R[100001];
int u[100001],v[100001],H[100001],dp[100001];
#define checkmin(x,c) do if((c)<(x)) (x)=(c); while(0)
int main(){
int n,m;
while(scanf("%d",&n)==1){
for(int i=0;i<n;i++) scanf("%d%d",&a[i].first,&a[i].second);
sort(a,a+n);
a[n].first=-1;
for(int i=m=0;i<n;i++)
if(a[i].first!=a[i+1].first) a[m++]=a[i];
int lat=-1,rat=-1,hat=-1;
L[++lat]=PII(-INF,-1);
R[++rat]=PII(+INF,+m);
H[++hat]=-1; H[++hat]=0;
for(int i=0;i<m;i++){
dp[i]=+INF;
for(u[i]=i;a[i].first-a[i].second<=L[lat].first;lat--)
u[i]=L[lat].second;
L[++lat]=PII(a[i].first,u[i]);
}
for(int i=m-1;~i;i--){
for(v[i]=i;a[i].first+a[i].second>=R[rat].first;rat--)
v[i]=R[rat].second;
R[++rat]=PII(a[i].first,v[i]);
}
dp[0]=dp[v[0]]=1;
for(int i=1;i<m;i++){
while(hat && H[hat-1]>=u[i]-1) hat--;
checkmin(dp[i],hat+1);
checkmin(dp[v[i]],dp[i-1]+1);
checkmin(hat,dp[i]-1);
H[++hat]=i;
}
printf("%d\n",dp[m-1]);
}
}
}}}/* 解题报告 //
给出 n 个木块，每个木块在 X[i] 的位置，高度为 H[i]
你可以将它们以朝左或朝右的方向推倒，会产生连锁反应
问至少要手动推倒多少块，才能完全使所有木块都倒下
首先，题目里的木块可能在相同的 X[i] 处，所以要先去重
对于有相同 X[i] 的木块，只保留 H[i] 最大的一个
然后用两个单调队列 L 和 R 去计算下面两个数组：
1. u[i] = 每个木块往左推倒，最远能碰倒的木块编号
2. v[i] = 每个木块往右推倒，最远能碰倒的木块编号
单调队列里面每个元素都是一个 pair<int, int>
表示在 first 的位置有一个木块，推倒它后最远能碰倒木块编号 second
每次在队列尾部新添加一个木块之前，先将它能碰倒的所有木块弹出队列
在此过程中，可以得到它能碰倒的最远木块编号，然后将它自己加入队列中
前面的预处理部分得到 u[] 和 v[] 数组后，就能用这两个数组进行 dp 了
用 dp[i] 表示弄倒了前 i 个木块所需要最少的手动推倒次数，转移方程是：
1. dp[i] = min(dp[i], min(dp[u[i] - 1] .. dp[i - 1]) + 1)
2. dp[i] .. dp[v[i]] = min(dp[i] .. dp[v[i]], dp[i - 1] + 1)
前一项是用连续的一段元素去更新一个元素
后一项是用一个元素去更新连续的一段元素
显然，这两个 dp 方程可以用线段树进行优化，达到 O(n log n) 的复杂度
不过我的做法是继续使用单调队列，在单调队列 H 中：
位置靠后的元素所需要的推倒次数必须大于靠前的
如果靠后的元素的值更小或相同，则靠前的元素没有存在的意义了
于是此时将靠前的弹出
如果只考虑前一项 dp 转移方程，非常简单，上面其实已经将做法全部写完了
每次添加新元素之前先维护单调队列，然后只要 dp[i] = size(H) + 1 即可
但现在有『可以向右推倒』这个条件的存在，所以需要进一步考虑
仔细观察后一项 dp 转移方程，发现它试图将一个区间的所有 dp 值
统一地改为某个特定的值，并且每次修改不会增加 dp 值，而只会降低
但我们的单调队列，对于相同的 dp 值，只会保留最靠后的一个
因此对于后一项 dp 转移方程，其实只要计算第 v[i] 个元素的值即可
其他元素的更新操作没有意义，因为到以后的某个时刻，那些值总会被弹出队列
所以现在也没必要计算了（重要的贪心优化）
对于每个木块 i，处理完两项 dp 方程后，最后将得到的 dp[i] 加入到队列中
并按上文中的方法去维护单调队列，弹出不必要的元素
我程序里的单调队列都是手工数组实现，主要是为了方便做一些操作
顺便说明一下，程序里名为 **at 的变量都是单调队列的队尾元素下标
// By 猛犸也钻地 @ 2012.07.27 */
#include <cstdio>
#include <algorithm>
using namespace std;
typedef pair<int,int> PII;
const int INF = 1000000007;
PII a[100001],L[100001],R[100001];
int u[100001],v[100001],H[100001],dp[100001];
#define checkmin(x,c) do if((c)<(x)) (x)=(c); while(0)
int main(){
int n,m;
while(scanf("%d",&n)==1){
for(int i=0;i<n;i++) scanf("%d%d",&a[i].first,&a[i].second);
sort(a,a+n);
a[n].first=-1;
for(int i=m=0;i<n;i++)
if(a[i].first!=a[i+1].first) a[m++]=a[i];
int lat=-1,rat=-1,hat=-1;
L[++lat]=PII(-INF,-1);
R[++rat]=PII(+INF,+m);
H[++hat]=-1; H[++hat]=0;
for(int i=0;i<m;i++){
dp[i]=+INF;
for(u[i]=i;a[i].first-a[i].second<=L[lat].first;lat--)
u[i]=L[lat].second;
L[++lat]=PII(a[i].first,u[i]);
}
for(int i=m-1;~i;i--){
for(v[i]=i;a[i].first+a[i].second>=R[rat].first;rat--)
v[i]=R[rat].second;
R[++rat]=PII(a[i].first,v[i]);
}
dp[0]=dp[v[0]]=1;
for(int i=1;i<m;i++){
while(hat && H[hat-1]>=u[i]-1) hat--;
checkmin(dp[i],hat+1);
checkmin(dp[v[i]],dp[i-1]+1);
checkmin(hat,dp[i]-1);
H[++hat]=i;
}
printf("%d\n",dp[m-1]);
}
}