prow2012-A3-0024

从 Trac 迁移的文章

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

原文章内容如下：

好题。用到了三次单调队列。
题意：一线排列的积木，每个积木有一定的高度，每个可以沿一个方向推倒，会引起连锁反应，问最少碰倒多少个可以推到全部。
{{{
首先求出往左推最远能碰倒的积木Left[i], 以及往右推最远能碰倒的积木Right[i]. （这步单调队列比较容易实现，不多说）

DP f[i] 表示编号1..i的积木全部推倒花费的最小次数

那么f[i] = min( f[Left[i]-1], .... , f[i-1]) +1

这里，只需要很直观的一个想法，假如j < k && f[j] > f[k]，那么j在之后的DP中将永远用不到了

所以，DP到i的时候，从后往前检查队列中的候选j，
如果j在i的可取范围内，直接把j踢出队列，因为DP值只增大1，只有最后一个踢出队列的需要保留，
所以有一个还原操作R++。

DP到i时，f[i-1] +1还有可能更新f[Right[i]]，而且只需要更新f[Right[i]]——因为前推的“贡献”次数只可能一次，
假设i-1贡献到中间值，那中间值也顶多贡献到Right[i](中间值也只能倒到Right[i]为止).

正是因为f[i]不仅是DP到i时求出的，我忽略了被前推贡献的情况，所以只在第一轮维护队列时踢是没踢干净的，
需要在第一轮踢完，补上最后的R++后，再根据f[i]的大小再踢一轮。在这里WA了3次。
}}}

{{{


#include <algorithm>
#include <stdio.h>
using namespace std;
#define maxn 101000
long long A[maxn],B[maxn],X[maxn],high[maxn];
bool cmp(int i,int j){
    if (A[i]==A[j]) return B[i]<B[j];
    else return A[i]<A[j];
}
int Left[maxn],Right[maxn],order[maxn];
int N,M;
int oo = 1000000000;
int f[maxn],Q[maxn];
int main(){
    int i,j;
    while(scanf("%d",&N)!=EOF){
        for (i=0;i<N;i++)
            order[i] = i,scanf("%lld%lld",&A[i],&B[i]);
        sort(order,order+N,cmp);
        order[N] = N;
        A[N] = -1;
        int M = 1;
        for (i=0;i<N;i++)
            if (A[order[i]]!=A[order[i+1]])
                X[M] = A[order[i]],high[M++] = B[order[i]];
        N = M;
        int L = 0,R = 0;
        Q[R++] = 1;
        Left[1] = 1;
        for (i=2;i<N;i++)
        {
            Left[i] = i;
            while(L<R&&(X[i]-X[Q[R-1]]<=high[i]))
                R--,Left[i] = Left[Q[R]];
            Q[R++] = i;
        }
        L = R = 0;
        Q[R++] = N-1;
        Right[N-1] = N-1;
        for (i=N-2;i>0;i--){
            Right[i] = i;
            while(L<R&&(X[Q[R-1]]-X[i]<=high[i]))
                R--,Right[i] = Right[Q[R]];
            Q[R++] = i;
        }
       // for (i=1;i<N;i++)
         //   printf("%d :%d %d\n",i,Left[i],Right[i]);
        for (i=0;i<N;i++)
            f[i] = oo;
        f[0] = 0;
        L = 0,R = 0;
        Q[R++] = 0;
        for (i=1;i<N;i++){
            int tmp = -1;
            while(L<R&&Left[i]-1<=Q[R-1]) //第一次维护队列
                R--,tmp = f[Q[R]];
            if (tmp==-1){
                f[i] = min(f[i],f[i-1]+1);
            }else {
                R++;
                f[i] = min(f[i],tmp+1);
            }
            while(L<R&&f[Q[R-1]]>=f[i]) R--;  //第二次维护队列，这里WA了
            f[Right[i]] = min(f[Right[i]],f[i-1]+1);
            Q[R++] = i;
        }
        printf("%d\n",f[N-1]);
    }
}


}}}

好题。用到了三次单调队列。

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

首先求出往左推最远能碰倒的积木Left[i], 以及往右推最远能碰倒的积木Right[i]. （这步单调队列比较容易实现，不多说）
DP f[i] 表示编号1..i的积木全部推倒花费的最小次数
那么f[i] = min( f[Left[i]-1], .... , f[i-1]) +1
这里，只需要很直观的一个想法，假如j < k && f[j] > f[k]，那么j在之后的DP中将永远用不到了
所以，DP到i的时候，从后往前检查队列中的候选j，
如果j在i的可取范围内，直接把j踢出队列，因为DP值只增大1，只有最后一个踢出队列的需要保留，
所以有一个还原操作R++。
DP到i时，f[i-1] +1还有可能更新f[Right[i]]，而且只需要更新f[Right[i]]——因为前推的“贡献”次数只可能一次，
假设i-1贡献到中间值，那中间值也顶多贡献到Right[i](中间值也只能倒到Right[i]为止).
正是因为f[i]不仅是DP到i时求出的，我忽略了被前推贡献的情况，所以只在第一轮维护队列时踢是没踢干净的，
需要在第一轮踢完，补上最后的R++后，再根据f[i]的大小再踢一轮。在这里WA了3次。

#include <algorithm>
#include <stdio.h>
using namespace std;
#define maxn 101000
long long A[maxn],B[maxn],X[maxn],high[maxn];
bool cmp(int i,int j){
    if (A[i]==A[j]) return B[i]<B[j];
    else return A[i]<A[j];
}
int Left[maxn],Right[maxn],order[maxn];
int N,M;
int oo = 1000000000;
int f[maxn],Q[maxn];
int main(){
    int i,j;
    while(scanf("%d",&N)!=EOF){
        for (i=0;i<N;i++)
            order[i] = i,scanf("%lld%lld",&A[i],&B[i]);
        sort(order,order+N,cmp);
        order[N] = N;
        A[N] = -1;
        int M = 1;
        for (i=0;i<N;i++)
            if (A[order[i]]!=A[order[i+1]])
                X[M] = A[order[i]],high[M++] = B[order[i]];
        N = M;
        int L = 0,R = 0;
        Q[R++] = 1;
        Left[1] = 1;
        for (i=2;i<N;i++)
        {
            Left[i] = i;
            while(L<R&&(X[i]-X[Q[R-1]]<=high[i]))
                R--,Left[i] = Left[Q[R]];
            Q[R++] = i;
        }
        L = R = 0;
        Q[R++] = N-1;
        Right[N-1] = N-1;
        for (i=N-2;i>0;i--){
            Right[i] = i;
            while(L<R&&(X[Q[R-1]]-X[i]<=high[i]))
                R--,Right[i] = Right[Q[R]];
            Q[R++] = i;
        }
       // for (i=1;i<N;i++)
         //   printf("%d :%d %d\n",i,Left[i],Right[i]);
        for (i=0;i<N;i++)
            f[i] = oo;
        f[0] = 0;
        L = 0,R = 0;
        Q[R++] = 0;
        for (i=1;i<N;i++){
            int tmp = -1;
            while(L<R&&Left[i]-1<=Q[R-1]) //第一次维护队列
                R--,tmp = f[Q[R]];
            if (tmp==-1){
                f[i] = min(f[i],f[i-1]+1);
            }else {
                R++;
                f[i] = min(f[i],tmp+1);
            }
            while(L<R&&f[Q[R-1]]>=f[i]) R--;  //第二次维护队列，这里WA了
            f[Right[i]] = min(f[Right[i]],f[i-1]+1);
            Q[R++] = i;
        }
        printf("%d\n",f[N-1]);
    }
}