어제 온사이트에서 들은 에디토리얼 바탕으로 N시간 동안 삽질해서 푸는데 성공해서 풀이 작성함

먼저 i번 별의 좌표를 (xi, yi)라고 했을 때
Xi = xi + yi, Yi = xi - yi 라고 해보자

그럼 i번 별과 j번 별 사이의 거리는 다음과 같이 나타낼 수 있다
(이건 웰노운)
max(|Xi - Xj|, |Yi - Yj|)
= max(Xi - Xj , -Xi + Xj, Yi - Yj, -Yi + Yj)

dp[i][j]를 1번 별부터 j번 별까지 i개의 구간으로 나누었을 때 최대값으로 두자
그러면 다음 식을 세울 수 있다

dp[i][j] = max{
..  dp[i-1][k-1] + Xk - Xj,
..  dp[i-1][k-1] - Xk + Xj,
..  dp[i-1][k-1] + Yk - Yj,
..  dp[i-1][k-1] - Yk + Yj,
..  dp[i][j-1]
}
위의 4가지는 [k, j] 구간이 새로운 하나의 구간이 되는 경우이고,
마지막 1가지는 j번째 별이 j-1까지의 구간에 포함되어 값의 변화에 영향을 미치지 않는 경우이다

이를 아래처럼 바꿔보자

dp[i][j] = max{
..  (dp[i-1][k-1] + Xk) - Xj,
..  (dp[i-1][k-1] - Xk) + Xj,
..  (dp[i-1][k-1] + Yk) - Yj,
..  (dp[i-1][k-1] - Yk) + Yj,
..  dp[i][j-1]
}
이렇게 소괄호로 묶인 부분의 최대값을 관리해주면 k를 전부 볼 필요가 없어진다

위에서부터 차례로 dp1, dp2, dp3, dp4로 둔다고 치고
대표로 dp2만 한번 다음과 같이 정의해보자

dp2[i][j] = max(dp[i-1][k-1] - Xk)
= max(dp2[i][j-1], dp[i][j-1] - Xj)

주의할 점은 아직 구간을 하나도 만들지 않았을 때도 고려해야한다는 점이다
dp2[0][j] = max(dp2[0][j-1], -X[j])

음수가 될 수도 있다는 점에 유의하여 -inf를 초기값으로 잡도록 하자

이런 식으로 dp1, dp2, dp3, dp4를 각각 정의하면

dp[i][j] = max{
..  dp1[i-1][j] - Xj,
..  dp2[i-1][j] + Xj,
..  dp3[i-1][j] - Yj,
..  dp4[i-1][j] + Yj,
..  dp[i][j-1]
}

이렇게 dp테이블 크기 O(5nm), 전이 O(1)에 계산이 가능하다

다 쓰고보니까 세그트리 4개만들어서 풀수도 있는거 아닌가 하는 생각이 드는데 시간내에 돌아가는지 잘 몰루겠고...

작성에 실수가 있을 수 있으니 소스코드를 같이 첨부함