codeforces 527D D. Clique Problem(二分+线段树+贪心+dp)

77 阅读 0 评论 51 点赞

我是靠谱客的博主醉熏冬瓜，最近开发中收集的这篇文章主要介绍codeforces 527D D. Clique Problem(二分+线段树+贪心+dp)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目链接：

codeforces 527D

题目大意：

给出一些点的 $x_i和w_i$ ，当 $|x_i-x_j| geq w_i+w_j$ 的时候，两点间存在一条边，找出一个最大的集合，集合中的点两两之间存在边。

题目分析：

首先我们想要知道哪些点之间是存在边的， $|x_i-x_j| geq w_i+w_j$ 的绝对值符号去掉不影响边，因为不等式右边是加法，所以
$x i - x j \geq w i + w j \Rightarrow x i - w i \geq w j + x j$ $begin{align} & x_i-x_j geq w_i+w_j \ & Rightarrow x_i-w_i geq w_j+x_j end{align}$
所以我们可以先按照 $w_j+x_j$ 排序，那么xi，那么对于每个 $x_i$ ，我们只需要找到不大于 $x_i-w_i$ 的j中的dp值最大的那个转移即可。区间最大通过线段树维护。利用二分找到比 $x_i-w_i$ 小的最大的j，定为k
我们得到：
$d p [i] = max j = 0 k d p [j] + 1$ $dp[i] = max_{j=0}^{k} dp[j] + 1$
那么就是只考虑前面的这i个点得到的最大的点集的数量。

AC代码：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#define INF (1<<29)
#define MAX 200007

using namespace std;

int n;
struct Node
{
    int w,x;
    bool operator < ( const Node& a ) const
    {
        return w+x < a.w+a.x;
    }
}p[MAX];

int bsearch ( int i )
{
    int l = 0 , r = i-1 ,mid;
    while ( l != r )
    {
        mid = (l+r+1)>>1;
        if ( p[i].x - p[i].w < p[mid].x + p[mid].w ) r = mid-1;
        else l = mid;
    }
    return l;
}

struct Tree
{
    int l,r,maxn;
}tree[MAX<<2];

void build ( int u , int l , int r )
{
    tree[u].l = l;
    tree[u].r = r;
    tree[u].maxn = 0;
    if ( l == r ) return;
    int mid = l+r>>1;
    build ( u<<1 , l , mid );
    build ( u<<1|1 , mid+1 , r );
}

void push_up ( int u )
{
    tree[u].maxn = max ( tree[u<<1].maxn , tree[u<<1|1].maxn );
}

void update ( int u , int x , int v )
{
    int l = tree[u].l;
    int r = tree[u].r;
    if ( l == r )
    {
        tree[u].maxn = v;
        return;
    }
    int mid = l+r>>1;
    if ( x > mid ) update ( u<<1|1 , x , v );
    else update ( u<<1 , x , v );
    push_up ( u );
}

int query ( int u , int left , int right )
{
    int l = tree[u].l , r = tree[u].r;
    if ( left <= l && r <= right )
        return tree[u].maxn;
    int mid = l+r>>1;
    int ret = 0;
    if ( l <= mid && r >= left ) ret = query ( u<<1 , left , right );
    if ( left <= r && right > mid )
        ret = max ( ret ,query ( u<<1|1 , left , right ) );
    return ret;
}

int main ()
{
    while ( ~scanf ( "%d" , &n ))
    {
        for ( int i = 1 ; i <= n ; i++ )
            scanf ( "%d%d" , &p[i].x , &p[i].w );
        sort ( p+1 , p+n+1 );
        build ( 1 , 0 , n );
        update ( 1 , 0 , 0 );
        p[0].x = - INF;
        p[0].w = - INF;
        int ans = 0;
        for ( int i = 1 ; i <= n ; i++ )
        {
            int x = bsearch ( i );
            //dp[i] = dp[x]+1;
            int v = query ( 1 , 0 , x );
            update ( 1 , i , v+1 );
            ans = max ( v+1 , ans );
        }
        printf ( "%dn" , ans );
    }
}