cea   6년 전

국문 번역된 문제를 읽다가 이걸 어떻게 풀지 고민하고, 이게 땅을 묶는게 disjoint 부분집합으로 분할하는게 아니라 구간으로 분할하는 것이었으면 convex hull trick으로 쉬워지겠다고 생각하고 있었는데, 혹시나 해서 원문을 보니 "successive groups"라는 조건이 있어 구간으로 분할하는게 맞다는 것을 이해했습니다. 또, 힌트도 (1) / (4) / (2,3)을 (1) / (2,3) / (4)로 바꿔야 오해가 줄어들 것 같습니다.

jh05013   6년 전

구간 분할이 아닙니다. 실제 데이터는 땅이 정렬되어 있지 않습니다.

원문의 "purchase the land in successive groups"는 땅이 연속하다는 뜻이 아니라 땅을 그룹으로 나눠서 연속으로 산다는 뜻이고, 원문 힌트도 1 / 4 / 2+3 순서로 되어 있습니다.

cea   6년 전

땅이 연속적이다는 것이 아니라,

dp[p] = min_{q>p} { dp[q] + max_{p<=x<q}w[x] * max_{p<=x<q}h[x] }

와 같은 재귀식이 말이 되도록 인풋 데이터를 [0,n)이라는 구간으로 봤을때 이를 disjoint 구간으로 분할하는지 아니면 여러개의 개별 부분집합들로 분할하는지의 질문입니다.

cea   6년 전

제 질문이 애초에 땅을 그룹으로 나눠서 연속으로 산다는 의미 (즉, disjoint 구간으로 나누는 것)인지, 아니면 사는 n개를 disjoint한 부분집합으로 분할해서 사는 것인지 였습니다. 오해가 생기게 표현을 한 것 같네요.

jh05013   6년 전

그냥 부분집합입니다. 예를 들어 입력으로 주어진 땅의 순서가 섞여도 답은 500입니다.

댓글을 작성하려면 로그인해야 합니다.