#19693 Safety

slope trick 연습문제 이다.
기억이 휘발되기 전에 풀이를 써본다.
https://www.acmicpc.net/problem/19693

 

개인적으로 이 문제는 풀이를 보지 않고 푸는 거를 추천한다.
풀면서 slope trick에 대한 이해가 깊어졌다..

 

 

 

기본으로 배웠던 boj수열 문제와는 다르게 함수의 왼쪽 오른쪽 구간을 동시에 관리해야 한다.
우선 $dp(x,y)=min(dp(x-1,y))+|a(x)-x|$가 된다. 단 ($x-k<=y<=x+k$) 

이를 이용해야 하는데 우선 확장된다는 점은 생각하지 말고, pq를 이용해서, 
min값을 유지시키는 x좌표를 어떻게 항상 handling 할지를 생각해보자.
2개를 동시에 관리하면 된다.

left,right2개를 만들고(단, right는 greater) 적절히 handling 하자.

 

수열의 각 원소를 순회할 때마다 3가지 경우가 있다. ($x-k<=y<=x+k$ 이 조건때문에... 그래프가 적절히 양쪽으로 확장되는데 일단 이 생각은 접어두자)

 

1.전체 value가 최소가 되는 구간의 최솟값 보다 작은값

2.전체 vlaue가 최소가 되는 구간의 최댓값 보다 큰 값

3. 구간 안의 값

3번 경우에는 그냥 left,right 각각에 넣어주기만 하면 된다.

이제 1번 case를 생각해보자.

다음과 같은 쿼리와 동치이면서, left,right에 항상 구간의 양끝값이 보장된다.

right에 left top을 넣어준다
left를 pop한다
left에 2번 push한다.

끝.
2번 case도 반대로 동일하다.

그런데 여기서 추가로, 중간부분이 확장되는 부분과, 정답을 더해나가는 부분은 적절히 알아서 체크해가면 된다.
이 문제 풀정도면 알아서 될듯

 

 

솔직히 코드 올리고 싶은데 안 올릴 것이다.
boj수열1의 사실상 난이도는 매우 높은데, 구현이 간단하다.
그래서 정말 정말 어려운 개념이고, 문제인데도 그냥 무지성으로 구글링해서 코드 복붙해서 내는게 많은것 같다.
그렇게 많이 풀리다니 ㅋㅋ.. 참...