team2012-F3-sol-0024

从 Trac 迁移的文章

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

原文章内容如下：

{{{
题意：
给定一些玩具用坐标x和高度h表示，如果向左或向右推倒一个玩具(x,h)，那么在(x-h, x)或(x, x+h)的范围内的玩具均被推倒
这样会形成骨牌效应，问最少几次能推倒所有玩具。

解法：
首先要处理出每个玩具向左和向右最远能推到几号玩具lft[i]和rgt[i]
则lft[i] = min(lft[j] | x-h <= j < x), rgt[i] = max(rgt[j] | x < j <= x+h)
需要用线段树优化这个处理过程，然后设f[i]为推倒前i个玩具的最小次数，则

1) 若最后一块是向左倒的，有 f[i] = min(f[j]+1 | lft[i]-1 <= j < i)
2) 若最后一块是向右倒的，有 f[i] = min(f[j-1]+1 | rgt[j] >= i)

同样能够用线段树优化这个DP过程，总复杂度 O(nlogn)
}}}
{{{
#include <iostream>
#include <cstdio>
#include <utility>
#include <map>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
template<class T> bool takemin(T& a, T b) {bool Z=(a>b); if(Z)a=b; return Z;}
template<class T> bool takemax(T& a, T b) {bool Z=(a<b); if(Z)a=b; return Z;}

const int MAXN = 65536*4 + 100;
const int GETMIN = 0, GETMAX = 1, INFI = 2100000000;
int l[MAXN], r[MAXN], minn[MAXN], maxx[MAXN], lch[MAXN], rch[MAXN], mid[MAXN];
int n, flag, lft[MAXN], rgt[MAXN], f[MAXN], min2[MAXN];
PII toy[MAXN];
map<int, int> num;

void build(int rt, int ll, int rr)
{
    l[rt] = ll;
    r[rt] = rr;
    if(ll == rr)
    {
        minn[rt] = maxx[rt] = ll;
        min2[rt] = INFI;
        return;
    }
    lch[rt] = (rt << 1);
    rch[rt] = lch[rt] + 1;
    mid[rt] = (ll + rr) / 2;
    build(lch[rt], ll, mid[rt]);
    build(rch[rt], mid[rt] + 1, rr);
    minn[rt] = min(minn[lch[rt]], minn[rch[rt]]);
    maxx[rt] = max(maxx[lch[rt]], maxx[rch[rt]]);
    min2[rt] = INFI;
}

void update(int rt, int w, int v)
{
    if(l[rt] == r[rt])
    {
        if(flag == GETMIN)   minn[rt] = v;
        if(flag == GETMAX)   maxx[rt] = v;
        return;
    }
    if(w <= mid[rt])
        update(lch[rt], w, v);
    else
        update(rch[rt], w, v);
    maxx[rt] = max(maxx[lch[rt]], maxx[rch[rt]]);
    minn[rt] = min(minn[lch[rt]], minn[rch[rt]]);
}

int query(int rt, int ll, int rr)
{
    if(ll == l[rt] && rr == r[rt])
    {
        if(flag == GETMIN)
            return minn[rt];
        if(flag == GETMAX)
            return maxx[rt];
    }
    if(rr <= mid[rt])
        return query(lch[rt], ll, rr);
    if(ll > mid[rt])
        return query(rch[rt], ll, rr);

    int ret = query(lch[rt], ll, mid[rt]);
    if(flag == GETMAX)
        takemax(ret, query(rch[rt], mid[rt]+1, rr));
    if(flag == GETMIN)
        takemin(ret, query(rch[rt], mid[rt]+1, rr));
    return ret;
}

void update2(int rt, int ll, int rr, int v)
{
    if(ll == l[rt] && rr == r[rt])
    {
        takemin(min2[rt], v);
        return;
    }
    if(rr <= mid[rt])
        update2(lch[rt], ll, rr, v);
    else if(ll > mid[rt])
        update2(rch[rt], ll, rr, v);
    else
    {
        update2(lch[rt], ll, mid[rt], v);
        update2(rch[rt], mid[rt]+1, rr, v);
    }
}

int query2(int rt, int w)
{
    if(l[rt] == w && r[rt] == w)
        return min2[rt];
    if(w <= mid[rt])
        return min(query2(lch[rt], w), min2[rt]);
    if(w > mid[rt])
        return min(query2(rch[rt], w), min2[rt]);
}

void init_left()
{
    flag = GETMIN;
    for(int i = 1; i <= n; i++)
    {
        int x = toy[i].first, h = toy[i].second;
        PII tmp = make_pair(x-h, -1);
        int loc = lower_bound(toy+1, toy+n+1, tmp) - toy;
        lft[i] = query(1, loc, i);
        update(1, i, lft[i]);
    }
}

void init_right()
{
    flag = GETMAX;
    for(int i = n; i >= 1; i--)
    {
        int x = toy[i].first, h = toy[i].second;
        PII tmp = make_pair(x+h, INFI);
        int loc = lower_bound(toy+1, toy+n+1, tmp) - toy - 1;
        rgt[i] = query(1, i, loc);
        update(1, i, rgt[i]);
    }
}

void gao()
{
    f[0] = 0;
    flag = GETMIN;
    for(int i=1;i<=n;i++)
    {
        f[i] = query2(1, i);
        takemin(f[i], f[lft[i]-1] + 1);
        if(lft[i] != i)
            takemin(f[i], query(1, lft[i], i-1) + 1);
        update(1, i, f[i]);
        if(rgt[i] != i)
            update2(1, i+1, rgt[i], f[i-1]+1);
    }
}

int main()
{
    while(~scanf("%d", &n))
    {
        int tot = 0;
        num.clear();
        for(int i = 1; i <= n; i++)
        {
            int a, b;
            scanf("%d %d", &a, &b);
            PII tmp = make_pair(a, b);
            if(num[a] == 0)
            {
                toy[++tot] = tmp;
                num[a] = tot;
            }
            else
                takemax(toy[num[a]], tmp);
        }
        n = tot;
        sort(toy+1, toy+n+1);

        build(1, 1, n);
        init_left();
        init_right();
        gao();

        printf("%d\n", f[n]);
    }
    return 0;
}
}}}

题意：
给定一些玩具用坐标x和高度h表示，如果向左或向右推倒一个玩具(x,h)，那么在(x-h, x)或(x, x+h)的范围内的玩具均被推倒
这样会形成骨牌效应，问最少几次能推倒所有玩具。
解法：
首先要处理出每个玩具向左和向右最远能推到几号玩具lft[i]和rgt[i]
则lft[i] = min(lft[j] | x-h <= j < x), rgt[i] = max(rgt[j] | x < j <= x+h)
需要用线段树优化这个处理过程，然后设f[i]为推倒前i个玩具的最小次数，则
1) 若最后一块是向左倒的，有 f[i] = min(f[j]+1 | lft[i]-1 <= j < i)
2) 若最后一块是向右倒的，有 f[i] = min(f[j-1]+1 | rgt[j] >= i)
同样能够用线段树优化这个DP过程，总复杂度 O(nlogn)

#include <iostream>
#include <cstdio>
#include <utility>
#include <map>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
template<class T> bool takemin(T& a, T b) {bool Z=(a>b); if(Z)a=b; return Z;}
template<class T> bool takemax(T& a, T b) {bool Z=(a<b); if(Z)a=b; return Z;}
const int MAXN = 65536*4 + 100;
const int GETMIN = 0, GETMAX = 1, INFI = 2100000000;
int l[MAXN], r[MAXN], minn[MAXN], maxx[MAXN], lch[MAXN], rch[MAXN], mid[MAXN];
int n, flag, lft[MAXN], rgt[MAXN], f[MAXN], min2[MAXN];
PII toy[MAXN];
map<int, int> num;
void build(int rt, int ll, int rr)
{
    l[rt] = ll;
    r[rt] = rr;
    if(ll == rr)
    {
        minn[rt] = maxx[rt] = ll;
        min2[rt] = INFI;
        return;
    }
    lch[rt] = (rt << 1);
    rch[rt] = lch[rt] + 1;
    mid[rt] = (ll + rr) / 2;
    build(lch[rt], ll, mid[rt]);
    build(rch[rt], mid[rt] + 1, rr);
    minn[rt] = min(minn[lch[rt]], minn[rch[rt]]);
    maxx[rt] = max(maxx[lch[rt]], maxx[rch[rt]]);
    min2[rt] = INFI;
}
void update(int rt, int w, int v)
{
    if(l[rt] == r[rt])
    {
        if(flag == GETMIN)   minn[rt] = v;
        if(flag == GETMAX)   maxx[rt] = v;
        return;
    }
    if(w <= mid[rt])
        update(lch[rt], w, v);
    else
        update(rch[rt], w, v);
    maxx[rt] = max(maxx[lch[rt]], maxx[rch[rt]]);
    minn[rt] = min(minn[lch[rt]], minn[rch[rt]]);
}
int query(int rt, int ll, int rr)
{
    if(ll == l[rt] && rr == r[rt])
    {
        if(flag == GETMIN)
            return minn[rt];
        if(flag == GETMAX)
            return maxx[rt];
    }
    if(rr <= mid[rt])
        return query(lch[rt], ll, rr);
    if(ll > mid[rt])
        return query(rch[rt], ll, rr);
    int ret = query(lch[rt], ll, mid[rt]);
    if(flag == GETMAX)
        takemax(ret, query(rch[rt], mid[rt]+1, rr));
    if(flag == GETMIN)
        takemin(ret, query(rch[rt], mid[rt]+1, rr));
    return ret;
}
void update2(int rt, int ll, int rr, int v)
{
    if(ll == l[rt] && rr == r[rt])
    {
        takemin(min2[rt], v);
        return;
    }
    if(rr <= mid[rt])
        update2(lch[rt], ll, rr, v);
    else if(ll > mid[rt])
        update2(rch[rt], ll, rr, v);
    else
    {
        update2(lch[rt], ll, mid[rt], v);
        update2(rch[rt], mid[rt]+1, rr, v);
    }
}
int query2(int rt, int w)
{
    if(l[rt] == w && r[rt] == w)
        return min2[rt];
    if(w <= mid[rt])
        return min(query2(lch[rt], w), min2[rt]);
    if(w > mid[rt])
        return min(query2(rch[rt], w), min2[rt]);
}
void init_left()
{
    flag = GETMIN;
    for(int i = 1; i <= n; i++)
    {
        int x = toy[i].first, h = toy[i].second;
        PII tmp = make_pair(x-h, -1);
        int loc = lower_bound(toy+1, toy+n+1, tmp) - toy;
        lft[i] = query(1, loc, i);
        update(1, i, lft[i]);
    }
}
void init_right()
{
    flag = GETMAX;
    for(int i = n; i >= 1; i--)
    {
        int x = toy[i].first, h = toy[i].second;
        PII tmp = make_pair(x+h, INFI);
        int loc = lower_bound(toy+1, toy+n+1, tmp) - toy - 1;
        rgt[i] = query(1, i, loc);
        update(1, i, rgt[i]);
    }
}
void gao()
{
    f[0] = 0;
    flag = GETMIN;
    for(int i=1;i<=n;i++)
    {
        f[i] = query2(1, i);
        takemin(f[i], f[lft[i]-1] + 1);
        if(lft[i] != i)
            takemin(f[i], query(1, lft[i], i-1) + 1);
        update(1, i, f[i]);
        if(rgt[i] != i)
            update2(1, i+1, rgt[i], f[i-1]+1);
    }
}
int main()
{
    while(~scanf("%d", &n))
    {
        int tot = 0;
        num.clear();
        for(int i = 1; i <= n; i++)
        {
            int a, b;
            scanf("%d %d", &a, &b);
            PII tmp = make_pair(a, b);
            if(num[a] == 0)
            {
                toy[++tot] = tmp;
                num[a] = tot;
            }
            else
                takemax(toy[num[a]], tmp);
        }
        n = tot;
        sort(toy+1, toy+n+1);
        build(1, 1, n);
        init_left();
        init_right();
        gao();
        printf("%d\n", f[n]);
    }
    return 0;
}