[DP] LOJ#6307. '아례 국경일 2017 Day 1'Clique

2637 단어 DP

가설xi>xjxi>xj
그러면 ii와 jj 사이에 가장자리가 있는 조건은 xi-3-xj≥wi+wjxi-3-xj≥wi+wj
하나의 점을 하나의 구간으로 간주(xi-3-wi,xi+wi)(xi-3-w i,xi+w i)
그러면 두 점의 가장자리가 있는 조건은 두 점이 대표하는 구간이 중첩되지 않는다는 것이다
이 문제는 가장 많은 구간을 골라서 이 구간들이 두 개가 겹치지 않도록 하는 것으로 바뀌었다
이것은 고전적인 DP이다

#include 
#include 
#include 
#include 
#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;j1);
    f[i]+=ad[i];
  }
  printf("%d
",f[m]);
  return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

[BOJ]11048(python)

python 풀이 DP를 이용해 풀이 보통 이런 문제는 dfs나 bfs로 풀이하는 것이여서 고민을 했는데 이 문구 덕분에 DP 를 이용해 풀이할 수 있었다 뒤로 돌아가는 등의 경우를 고려하지 않아도 되기 때문이다 코...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다