[일반] 아 F 방금 다 짰는데

[캐티(tae826)]

이거 걍 겹치는거 빼고 바로 먹히는 구간 빼고

점 구간들 점 구간들 점 구간들 점 ... 

으로 나눠서 점 과 점 사이에 있는 애를 왼쪽 오른쪽 점 둘 중 하나로 누가 다 먹을지 결정하는거 아닌가?

아 아쉽다

[캐티(tae826)]

생각해보니까 이것도 아닌것 같네 아 어케 짜야되냐

[ㅁ(119.202)]

말대로 점을 이미 포함한 구간은 날려버려서 어떤 구간도 어떤 점을 포함하지 않게 문제를 줄인뒤, 왼쪽부터 오른쪽으로 읽으며 DP

[캐티(tae826)]

근데 dp하면 N^2 나오지 않나?

[캐티(tae826)]

아 아니네 시발

[ㅁ(119.202)]

N개의 event가 있다고 할때 제일 왼쪽에 있는 점이 <- -> 이렇게 움직였느냐 -> <- 이렇게 움직이느냐에 따라 거리x1을 더해주느냐 거리x2를 더해주느냐가 결정되기 때문에 점의 state는 사실 2개뿐임. 그래서 2N크기의 DP

[캐티(tae826)]

ㅇㅇ 어케하는지 알 것 같음.. 시간 30분만 더 있었으면 풀었을거 같은데 D2에서 너무 말려서