2012-A3-0024

从 Trac 迁移的文章

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

原文章内容如下：

题意：一线排列的积木，每个积木有一定的高度，每个可以沿一个方向推倒，会引起连锁反应，问最少碰倒多少个可以推到全部。

按x坐标排序是必不可少的。

先预处理出，两个方向推到一个，可以推到到对应方向的最远位置,l[i],r[i],最坏O(n^2^)可以预处理出来，

于是很容易想出O(n^2^)的DP,f[i]表示从左至右推倒到i最少要碰倒几个. f[i] = min(f[l[i]-1]+1,f[i]),再以之f[i]+1更新f[j, j from i+1 to r[i]]. 

这样可以n^2^解决这个问题，同时预处理和DP的过程都可以用线段树优化到O(n log n),这样就可以在O(n log n)解决这个问题。

实际上，不算排序，可以用O(n)的方法，解决它，实现也比较简单。

L[i]和R[i]意义和上面一样，需要预处理，

注意到，每次推到如果引起连锁反应，必然只需要找到它只靠自己能推的最远的位置，剩下的要靠它推倒的积木的连锁反应来延续，

于是只要利用之前算过的L[i]或R[i],就可不必模拟全部的骨牌效应，这样路径压缩了，就可以在O(n)的时间预处理出来。

之后的DP，f[i]的含义仍和上面相同，不同之处在于存下，最近用了f[j]的值是在那个j，只要这个j在l[i]到i的范围内，就可以用来更新f[i]

{{{
#include<cstdio>
#include<algorithm>
using namespace std;
typedef unsigned u32;
#define X first
#define H second
pair<u32,u32> b[102400];
u32 r[102400],l[102400],f[102400],m[102400];
int main(){
    for(u32 n;~scanf("%u",&n);){
        for(size_t i=0;i<n;++i){
            scanf("%u%u",&b[i].X,&b[i].H);
            b[i].X+=1000000000u;
        }
        sort(b,b+n);
        for(u32 i=n,k;i--;r[i]=k)
            for(k=i;k+1<n&&b[i].X+b[i].H>=b[k+1].X;k=r[k+1]); 
        for(u32 i=0,k;i<n;l[i++]=k)
            for(k=i;k&&b[i].X-b[i].H<=b[k-1].X;k=l[k-1]);
        for(u32 i=0;i<=n;++i){f[i]=i;m[i]=0;}
        for(u32 i=0;i<n;++i){
            if(f[i]<f[r[i]+1])f[r[i]+1]=f[i]+1;
            u32 j=l[i],k=f[i];
            for(;k && m[k-1]>=j;--k);
            if(k<f[i+1])f[i+1]=k+1;
            m[f[i+1]]=i+1;
        }
        printf("%u\n",f[n]);
    }
    return 0;
}
}}}

题意：一线排列的积木，每个积木有一定的高度，每个可以沿一个方向推倒，会引起连锁反应，问最少碰倒多少个可以推到全部。

按x坐标排序是必不可少的。

先预处理出，两个方向推到一个，可以推到到对应方向的最远位置,l[i],r[i],最坏O(n²)可以预处理出来，

于是很容易想出O(n²)的DP,f[i]表示从左至右推倒到i最少要碰倒几个. f[i] = min(f[l[i]-1]+1,f[i]),再以之f[i]+1更新f[j, j from i+1 to r[i]].

这样可以n²解决这个问题，同时预处理和DP的过程都可以用线段树优化到O(n log n),这样就可以在O(n log n)解决这个问题。

实际上，不算排序，可以用O(n)的方法，解决它，实现也比较简单。

L[i]和R[i]意义和上面一样，需要预处理，

注意到，每次推到如果引起连锁反应，必然只需要找到它只靠自己能推的最远的位置，剩下的要靠它推倒的积木的连锁反应来延续，

于是只要利用之前算过的L[i]或R[i],就可不必模拟全部的骨牌效应，这样路径压缩了，就可以在O(n)的时间预处理出来。

之后的DP，f[i]的含义仍和上面相同，不同之处在于存下，最近用了f[j]的值是在那个j，只要这个j在l[i]到i的范围内，就可以用来更新f[i]

#include<cstdio>
#include<algorithm>
using namespace std;
typedef unsigned u32;
#define X first
#define H second
pair<u32,u32> b[102400];
u32 r[102400],l[102400],f[102400],m[102400];
int main(){
    for(u32 n;~scanf("%u",&n);){
        for(size_t i=0;i<n;++i){
            scanf("%u%u",&b[i].X,&b[i].H);
            b[i].X+=1000000000u;
        }
        sort(b,b+n);
        for(u32 i=n,k;i--;r[i]=k)
            for(k=i;k+1<n&&b[i].X+b[i].H>=b[k+1].X;k=r[k+1]); 
        for(u32 i=0,k;i<n;l[i++]=k)
            for(k=i;k&&b[i].X-b[i].H<=b[k-1].X;k=l[k-1]);
        for(u32 i=0;i<=n;++i){f[i]=i;m[i]=0;}
        for(u32 i=0;i<n;++i){
            if(f[i]<f[r[i]+1])f[r[i]+1]=f[i]+1;
            u32 j=l[i],k=f[i];
            for(;k && m[k-1]>=j;--k);
            if(k<f[i+1])f[i+1]=k+1;
            m[f[i+1]]=i+1;
        }
        printf("%u\n",f[n]);
    }
    return 0;
}