[CF 528B] Clique Problem

作法：

這題的關鍵是注意到，如果有 x < y < z ，滿足 x 和 y 連邊，且 y 和 z 連邊，那麼 x 就和 z 連邊，證明並不難。因此我們只要找一個最長的子序列，使得相鄰的兩個點都有連邊就可以了。而這顯然可以DP，設 dp[ i ] 代表以 i 結尾的最長相鄰兩點有連邊的最長子序列的長度，那麼可以用 dp[ j ] 轉移 dp[ i ] 的條件就是 w[ i ] + w[ j ] <= p[ i ] - p[ j ] ，移項得 p[ i ] - w[ i ] >= w[ j ] + p[ j ] ，因此對於每個 j ，紀錄一個二元組 ( dp[ j ] , w[ j ] + p[ j ] ) ，並且可以知道，如果一個數的 dp 值比較小，但 w + p 的值比較大，那麼他就廢掉了，因此可以維護一個兩個座標都是遞增的二元組的 set ，查詢時對他查詢比 p[ i ] - w[ i ] 小的最大 w[ j ] + p[ j ] 值，他的 dp 值 +1 就是這個數的 dp 值。

code :

#include<bits/stdc++.h>
#define INF 1500000000
using namespace std;
const int maxn=200000+10 ;
 
struct P
{
    int x,y ;
    bool operator < (const P &rhs) const
    {
        return x==rhs.x ? y>rhs.y : x<rhs.x ;
    }
};
 
set<P> st ;
void insert(const P &p)
{
    st.insert(p) ; auto it=st.find(p) ;
    bool keep=1 ;
    if(it!=st.begin())
    {
        it-- ;
        if(it->y >= p.y) keep=0 ;
        it++ ;
    }
    if(!keep) { st.erase(it) ; return ; }
    while(1)
    {
        auto it2=it ; it2++ ;
        if(it2!=st.end() && it2->y<=p.y)
            st.erase(it2) ;
        else break ;
    }
}
 
P a[maxn] ;
main()
{
    int n ; scanf("%d",&n) ;
    for(int i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y) ;
    sort(a+1,a+n+1) ;
 
    insert((P){-INF,0}) ;
    int ans=0 ;
    for(int i=1;i<=n;i++)
    {
        auto it=st.upper_bound((P){a[i].x-a[i].y,-INF}) ; it-- ;
        int val=it->y+1 ; ans=max(ans,val) ;
        insert((P){a[i].x+a[i].y,val}) ;
    }
    printf("%d\n",ans) ;
}