[JOI Open 2014] PinBall

https://oj.uz/problem/view/JOI14_pinball

문제

i번째에  사이에 있는 모든 좌표들을  로 보내버리는 핀볼 막대기가 위치하고, 각 막대기를 한 번 탈때마다 D_i의 비용이 듭니다.

이 때, 어떤 좌표에서 떨어트려도 똑같은 좌표로 놓게 하는 핀볼의 배치 중에서, 최소의 비용이 드는 핀볼의 위치의 배치를 찾아서 그 비용이 얼마인지를 구하여라.

관찰

이 문제를 그냥 아무 생각 없이 보면 상당히 복잡한 시뮬레이션 게임처럼 보인다. 하지만, 일종의 가정을 하고 나면 그 순간부터는 생각보다 간단한 문제로 바뀐다.

공의 최종 위치를 항상 단조 증가하게 막대기를 놓는다고 하자. 

이렇게 하면, 결론적으로 모든 공이 다 한쪽으로 모이기 위해선, 1번 공과 N번 공이 똑같은 곳으로 모이면 된다.

나오는 출구의 좌표는 절대 감소하지 않기 때문에, 1번공과 N번공이 어떤 막대기들의 배치를 따라서 똑같은 곳으로 모였다는 것은 나머지 좌표들도 똑같은 곳으로 모이게 된다.

약간 압축 정리 같은 느낌이라고 보면 될듯?

어찌 됐든, 이를 이용해서 구한다.

A[i] = 1번공이 i번 장치에 도달하기 위해 드는 최소 비용

B[i] = N번공이 i번 장치에 도달하기 위해 드는 최소 비용

A[i] = Min(A[j]), B[i]=Min(B[j])가 된다

j는 A_i와 B_i사이에 존재하는 C_j를 만족하는 수들이고

이는 세그먼트 트리를 통해서 관리해줄 수 있다.

최종적으로 이 막대기를 통과했을 때 드는 최소 비용은 A[i]+B[i]+D_i가 될것이고,

이것의 최소값이 답이 될것이다.

이를 바탕으로 구현한 코드는 다음과 같다.

코드

https://oj.uz/submission/53081