邪恶的大叔（原题：多米诺骨牌）
题目描述
一个邪恶的大叔（小鸟游星野）进入了这个神秘的空间，他发现这里有很多很多的 Loli 在这里，这个邪恶的大叔想把她们全部推倒！但是推倒 Loli 要耗费的体力太大了，所以他想用尽量少的次数把他们全部推倒。
所有的 Loli 可以抽象成一个一维的坐标系，第 \(i\) 个 Loli 所在的位置为 \(X_i\)，她的身高为 \(H_i\)。大叔可以推倒任意个 Loli 让她们向左或者向右倒下去，第 \(i\) 个 Loli 倒下去之后可能会连带着别的 Loli 一起倒下去（向左倒就是在她左边并且满足 \(|X_i-X_j| \leq H_i\) 的所有 Loli 也会一起向左倒，向右同样计算）。
你的任务是帮助大叔计算出最少推倒多少个 Loli 可以让所有的 Loli 全部倒下。
输入描述
第一行一个整数 \(N\)，表示 Loli 的个数。
以下 \(N\) 行每行两个整数 \(X_i\)、\(H_i\)，分别表示第 \(i-1\) 个 Loli 的位置和她的身高。
输入保证 \(X_i\) 递增输入。
输出描述
输出一行一个整数，表示大叔最少推倒的次数。
输入输出样例 #1
输入样例 #1
6
1 1
2 2
3 1
5 1
6 1
8 3
输出样例 #1
2
说明/提示
样例 #1 解释
向右推倒第 \(1\) 个Loli可以让第 \(2\)、\(3\) 个 Loli一起倒下。
向左推倒第 \(6\) 个Loli可以让第 \(4\)、\(5\) 个 Loli一起倒下。
数据范围
对于 \(30\)% 的数据，满足 \(N \leq 10\)。
对于 \(50\)% 的数据，满足 \(N \leq 1000\)。
对于\(100\)% 的数据，满足 \(N \leq 100000\)，\(H_i \leq 10^8\)，\(X_i \leq 2^{31}\)。
解题报告
孩子们，贪心又双叒叕假了。
一个前 \(50\)% 数据放了四大洋的题。
可以先预处理出从每个点左推和右推可以到达的最远距离，方法是根据已知结果跳跃求解。具体的，如果把点 \(i\) 推倒后可以推倒 \(j\)，就尝试从点 \(j\) 可以推倒的最远处的下一个位置继续推。
设从第 \(i\) 点向左推可以推倒的最远点为 \(lp_i\)，向右推可以推倒的最远点为 \(rp_i\)。
直接考虑动态规划。设 \(dp[i][0/1]\) 表示把区间 \([1,i]\) 内的 Loli 全部推倒，并且第 \(i\) 个 Loli 向左/右倒所需的最小操作数。
下面考虑怎么转移。
-
对于 \(dp[i][0]\)，显然能退多远就推多远是最优的，\(dp[i][1]=\min(dp[lp_i-1][0],dp[lp_i-1][1])+1\)。
-
对于 \(dp[i][1]\)，需要分讨点 \(i\) 是被之前的点连锁推倒还是自己被推倒两种情况，两者取最小值。
- 点 \(i\) 自己向右倒，显然无法和之前产生联系，于是只需 \(dp[i][1]=\min(dp[i-1][0],dp[i-1][1])+1\)。
- 点 \(i\) 被之前的点推向右倒，则：\(dp[i][1]=\min_{rp_j \geq i}( dp[j][1] )\)。
在实际实现中，我们不是去找 \(j\)，而是用 \(i\) 向右倒的产生价值更新所有 \(k \in [i,rp_i]\) 中的 \(dp[k][1]\) ，这样做是等价的。
显然，可以用线段树维护，区间 \(\text{ckmin}\) 和单点查询。
代码如下：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int INF=0x3f3f3f3f;
const int N=201100;#define ckmax(x,y) ( x=max(x,y) )
#define ckmin(x,y) ( x=min(x,y) )inline int read()
{int f=1,x=0; char ch=getchar();while(!isdigit(ch)) { if(ch=='-') f=-1; ch=getchar(); }while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar(); }return f*x;
}int n,x[N],h[N];
int lp[N],rp[N];
int dp[N][2];inline void Prepare()
{for(int i=1;i<=n;i++) lp[i]=rp[i]=i;for(int i=2;i<=n;i++){int k=i;while(lp[k]!=1 && x[i]-x[lp[k]-1]<=h[i])k=lp[k]-1;lp[i]=lp[k];}for(int i=n-1;i>=1;i--){int k=i;while(rp[k]!=n && x[rp[k]+1]-x[i]<=h[i])k=rp[k]+1;rp[i]=rp[k];}
}#define iL i<<1
#define iR i<<1|1struct node
{int val,tag;
}T[N<<2];inline void pushup(int i)
{ T[i].val=min(T[iL].val,T[iR].val); }void build(int i,int l,int r)
{T[i].val=T[i].tag=INF;if(l==r) return ;int mid=l+r>>1;build(iL,l,mid);build(iR,mid+1,r);
}inline void pushdown(int i)
{if(T[i].tag==INF) return ;ckmin(T[iL].val,T[i].tag),ckmin(T[iL].tag,T[i].tag);ckmin(T[iR].val,T[i].tag),ckmin(T[iR].tag,T[i].tag);T[i].tag=INF;
}void update(int i,int l,int r,int L,int R,int x)
{if(L<=l && r<=R){ckmin(T[i].val,x);ckmin(T[i].tag,x);return ;}pushdown(i);int mid=l+r>>1;if(L<=mid) update(iL,l,mid,L,R,x);if(R>mid) update(iR,mid+1,r,L,R,x);pushup(i);
}int query(int i,int l,int r,int pos)
{if(l==r) return T[i].val;pushdown(i);int mid=l+r>>1;if(pos<=mid) return query(iL,l,mid,pos);if(pos>mid) return query(iR,mid+1,r,pos);
}signed main()
{freopen("push.in","r",stdin);freopen("push.out","w",stdout);n=read();for(int i=1;i<=n;i++)x[i]=read(),h[i]=read();Prepare(); build(1,1,n);for(int i=1;i<=n;i++){dp[i][0]=min(dp[lp[i]-1][0],dp[lp[i]-1][1])+1;dp[i][1]=min(dp[i-1][0],dp[i-1][1])+1;ckmin(dp[i][1],query(1,1,n,i));update(1,1,n,i,rp[i],dp[i][1]);}printf("%lld\n",min(dp[n][0],dp[n][1]));return 0;
}