Codeforces #39C: Moon Craters 문제 해결

이 문제는 딱 봐도 dp인데 어떻게 해야 할지 모르겠다
처음에 dp[i]를 생각해 봤는데 앞의 i개의 원 중에서 서로 겹치지 않는 것을 최대 몇 개까지 선택할 수 있음을 나타낸다. 원을 먼저 오른쪽 단점에 따라 정렬한다.그러나 원의 크기의 임의성 때문에 dp가 정확하지 않다
나중에 되게 복잡한 dp를 생각해 봤어요.
먼저 원의 오른쪽 끝점에 따라 작은 것에서 큰 것으로 정렬하고 오른쪽 끝점은 같은 반경 크기에 따라 작은 것에서 큰 것으로 정렬한다. 이렇게 하면 i번째 원을 고려할 때 그는 앞의 원에 포함되거나 앞의 원에 내접될 수 없다.
정렬된 원 배열에 대해 먼저 두 가지 사전 처리를 수행합니다.
1. 원 i에 대해 오른쪽 단점이 왼쪽 단점 왼쪽에 있고 왼쪽 단점에서 가장 가까운 원의 번호를 기록한다(약간 구부러진 부분). 만약 여러 개의 거리가 반경이 가장 큰 것을 기록한다면 이 수조는 nleft[i]라고 기록한다.
2. 원 i에 대해 왼쪽 단점이 왼쪽 단점 오른쪽에 있고 왼쪽 단점에서 가장 가까운 원의 번호를 기록한다. 만약 여러 개의 거리가 같으면 아무거나 기록한다. 이 수조는 nright[i]라고 기록한다.
이 두 예처리 모두 set+upperbound 같은 기술이 됐어요.
그리고 dp[i][j]를 기억하세요. 현재 i번째 원을 고려하여 얻은 모든 원 중 가장 왼쪽의 원의 왼쪽 경계는 원수 그룹 중 j번째 원의 왼쪽 경계의 오른쪽에 있습니다. 상기 조건을 충족시키기 위해 얻을 수 있는 가장 많은 원의 개수(복잡한 상태입니다)
옮기는 건 i번 원에서 뽑을지 안 뽑을지 보는 거예요.
만약 i번째 원을 찾지 않는다면 분명히 dp[i][j]=dp[i-1][j]
만약 i번째 원을 얻는다면 먼저 i번째 원의 왼쪽 단점이 j번째 원의 왼쪽 단점의 오른쪽에 있는 것을 만족시켜야 한다.정렬 방법으로 알 수 있듯이 그가 앞의 원에 포함되거나 앞의 원에 내접될 수 없기 때문에 가장 많이 얻을 수 있는 원은 한편으로는 i번째 원의 왼쪽 단점 왼쪽의 일련의 원, 즉 dp[nleft[i][j]이고 다른 한편으로는 원 i에 포함된 일련의 원, 즉 dp[i-1][nright[i]이다. dp의 상태에서 볼 수 있듯이 왼쪽 단점이 같은 원에 대응하는 j의 dp값은 같아야 한다.그래서 nright[i]는 기록할 때 아무거나 적어도 돼요.
총괄적으로 말하면 dp[i][j]=max(dp[i-1][j], dp[i-1][nright[i]]]+dp[nleft[i]][j])
O(nlogn)의 예처리, O(n*n)의 상태수, O(1)의 전이이기 때문에 총 복잡도는 O(n*n)이다.
난잡하게 쓴 것 같은데...코드 붙여주세요.

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include