[DP] LOJ#6307. 「雅礼国庆 2017 Day1」Clique

假设 $x_i>x_j$

那么 $i$ 和 $j$ 之间有边的条件是 $x_i-x_j\ge w_i+w_j$

把一个点看作一个区间 $(x_i-w_i,x_i+w_i)$

那么两个点有边的条件就是两个点代表的区间不重叠

这题就转化成选出最多从区间使得这些区间两两不重叠

这是个经典的DP

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#define ALL(x) (x).begin(),(x).end()

using namespace std;

const int N=400010;

int n,x[N],w[N],l[N],r[N],f[N],ad[N];

vector<int> sb,t[N];

int main(){
  scanf("%d",&n);
  for(int i=1;i<=n;i++){
    scanf("%d%d",&x[i],&w[i]); 
    l[i]=x[i]-w[i]; r[i]=x[i]+w[i];
    sb.push_back(l[i]); sb.push_back(r[i]);
  }
  sort(ALL(sb)); sb.erase(unique(ALL(sb)),sb.end());
  for(int i=1;i<=n;i++){
    l[i]=lower_bound(ALL(sb),l[i])-sb.begin()+1;
    r[i]=lower_bound(ALL(sb),r[i])-sb.begin()+1;
    if(l[i]==r[i]) ad[r[i]]++;
    else t[r[i]].push_back(l[i]);
  }
  int m=sb.size();
  for(int i=1;i<=m;i++){
    f[i]=f[i-1];
    for(int j=0;j<t[i].size();j++)
      f[i]=max(f[i],f[t[i][j]]+1);
    f[i]+=ad[i];
  }
  printf("%d\n",f[m]);
  return 0;
}