NC15556. 小Y与多米诺骨牌
描述
小Y用一副高度不一的多米诺骨牌摆成了一排直线，一共N张骨牌，其中第i张骨牌在直线上的坐标为，高度为
，任意两张骨牌的X坐标都不相同。摆完之后他发现，推倒一张骨牌并不一定能够让所有牌都连续倒下，于是他想知道最少要直接推倒多少张牌（向左向右皆可），才能让所有牌直接或间接被推倒。
骨牌的厚度不计，也就是说，比如向右（X轴正方向）推倒骨牌i时，则当骨牌j满足时会被间接地向右推倒(同理，向左时需要满足
)。
输入描述
多组数据，第一行一个整数
表示数据组数。
接着有T组数据，每组数据第一行有一个整数
表示骨牌数量，
之后N行每行有两个整数
表示骨牌的X坐标和高度
，给出的坐标按顺序严格递增。
输出描述
对于每组数据，在一行中输出一个整数，表示最少需要直接推倒的骨牌数量。
示例1
输入:
2 3 1 3 4 2 5 2 3 1 3 4 3 7 7
输出:
2 1
说明:
第一组样例，需要推倒第一个骨牌，然后向右推倒第二个骨牌即可。C++14(g++5.4) 解法, 执行用时: 1132ms, 内存消耗: 3420K, 提交时间: 2019-09-16 22:04:58
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#define lson k<<1,l,mid
#define rson k<<1|1,mid+1,r
#define inf 0x3f3f3f3f
using namespace std;
const int MX=1e5+9;
int T,n,x[MX],h[MX],t[MX<<2],l[MX],r[MX],f[MX];
void build(int k,int l,int r){
if( l==r ){
t[k]=inf;
return ;
}
int mid=(l+r)>>1;
build(lson);
build(rson);
t[k]=min(t[k<<1],t[k<<1|1]);
}
void update(int k,int l,int r,int pos,int val){
if( l==r ){
t[k]=min(t[k],val);
return ;
}
int mid=(l+r)>>1;
if( pos<=mid )
update(lson,pos,val);
else
update(rson,pos,val);
t[k]=min(t[k<<1],t[k<<1|1]);
}
int query(int k,int l,int r,int L,int R){
if( L<=l && r<=R )
return t[k];
int mid=(l+r)>>1,ans=inf;
if( L<=mid )
ans=min(ans,query(lson,L,R));
if( mid<R )
ans=min(ans,query(rson,L,R));
return ans;
}
int main()
{
// freopen("input.txt","r",stdin);
scanf("%d",&T);
while( T-- ){
scanf("%d",&n);
for( int i=1 ; i<=n ; i++ )
scanf("%d %d",&x[i],&h[i]);
build(1,1,n);
for( int i=1 ; i<=n ; i++ ){
int p=upper_bound(x+1,x+1+n,x[i]-h[i])-x;
// printf("%d ",p);
l[i]=(p==i)?i:query(1,1,n,p,i);
update(1,1,n,i,l[i]);
}
// printf("\n");
build(1,1,n);
for( int i=n ; i>=1 ; i-- ){
int p=lower_bound(x+1,x+1+n,x[i]+h[i])-x-1;
// printf("%d ",p);
r[i]=(p==i)?i:-query(1,1,n,i,p);
update(1,1,n,i,-r[i]);
}
// printf("\n");
// for( int i=1 ; i<=n ; i++ )
// printf("l[%d]:%d%c",i,l[i],i==n?'\n':' ');
// for( int i=1 ; i<=n ; i++ )
// printf("r[%d]:%d%c",i,r[i],i==n?'\n':' ');
build(1,1,n);
for( int i=1 ; i<=n ; i++ ){
f[i]=min(f[l[i]-1],query(1,1,n,i,n))+1;
update(1,1,n,r[i],f[i-1]);
}
// for( int i=1 ; i<=n ; i++ )
// printf("%d%c",f[i],i==n?'\n':' ');
// printf("\n");
printf("%d\n",f[n]);
}
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 1354ms, 内存消耗: 3912K, 提交时间: 2018-04-25 23:11:12
#include <bits/stdc++.h>
using namespace std;const int inf=0x3f3f3f3f;const int maxn=100005;int T,n,x[maxn],y[maxn],l[maxn],r[maxn],s[maxn<<2],f[maxn];inline void build() {for (int i=1;i<(n<<2);++i)s[i]=inf;}void update(int x,int l,int r,int p,int v) {if (l==r) {s[x]=min(s[x],v);return;}int m=(l+r)>>1;if (m>=p) update(x<<1,l,m,p,v);else update(x<<1|1,m+1,r,p,v);s[x]=min(s[x<<1],s[x<<1|1]);}int query(int x,int l,int r,int L,int R) {if (L<=l&&R>=r) return s[x];int m=(l+r)>>1,ret=inf;if (m>=L) ret=min(ret,query(x<<1,l,m,L,R));if (m<R) ret=min(ret,query(x<<1|1,m+1,r,L,R));return ret;}int main(){scanf("%d",&T);while (T--) {scanf("%d",&n);for (int i=1;i<=n;++i)scanf("%d%d",&x[i],&y[i]);build();for (int i=1;i<=n;++i) {int p=upper_bound(x+1,x+1+n,x[i]-y[i])-x;update(1,1,n,i,l[i]=(p==i)?i:query(1,1,n,p,i-1));}for (int i=n;i>=1;--i) {int p=lower_bound(x+1,x+1+n,x[i]+y[i])-x-1;update(1,1,n,i,-(r[i]=(p==i)?i:-query(1,1,n,i+1,p)));}build();for (int i=1;i<=n;++i) {f[i]=min(f[l[i]-1],query(1,1,n,i,n))+1;update(1,1,n,r[i],f[i-1]);}printf("%d\n",f[n]);}return 0;}