[codeforces] 1942D. Learning to Paint

문제 링크

$n$개의 칸이 일렬로 나열된 캔버스를 칠하고자 합니다. 각 칸은 전체를 칠하거나 완전히 칠하지 말아야 합니다. 그리고 $n \times n$크기의 2차원 배열 $a$가 주어집니다. 캔버스의 색칠된 칸의 구간이 $[l_{1}, r_{1}], [l_{2}, r_{2}], \cdots, [l_{k}, r_{k}]$라고 할 때, 색칠의 아름다움은 $\displaystyle\sum_{i=1}^{k}{a_{l_{i}, r_{i}}}$로 계산합니다. 단, 아름다움을 계산할 때 서로 다른 두 구간 사이에는 적어도 색칠되지 않은 칸이 하나 이상 있어야 합니다. (즉, 서로 다른 두 구간은 서로 붙어 있으면 안됩니다.) 저희의 목표는 칸을 색칠하는 $2^{n}$가지의 방법 중 아름다움의 값이 가장 큰 $k$개의 값을 출력하는 것입니다.

먼저 $dp[i][j]$를 $i$번째 칸까지 고려했을 때, $j$번째로 큰 아름다움의 값으로 정의 하겠습니다. 그리고 multiset $S_{i}$를 다음과 같이 정의합니다.

$S_{i}$를 내림차순으로 정렬한 것을 $\{ s_{i, 1}, s_{i, 2}, \cdots \}$라고 한다면 $dp[i][j]$는 다음을 만족합니다.

$S_{i}$의 원소의 갯수는 $O(i^2k)$이므로 각 $S_{i}$를 Naive하게 구하는 방법은 사용할 수 없습니다. 하지만 우리는 가장 큰 $k$개의 값만 구하면 되므로 $S_{i}$를 잘 쪼개서 각 집합 조각에서 큰 값부터 살펴보면서 $k$개의 값을 찾아나가는 방법을 사용할 수 있습니다.

자세한 과정은 다음과 같습니다.

1. $0, \max(dp[x]), \max(dp[x] + a[x+2][i])$를 뽑습니다.
2. 다음 과정을 $k$번 반복합니다.
   $\quad$ 2-1. 최댓값을 뽑아 $dp[i]$에 담습니다. 현재 과정이 $j$번째 이루어지고 있는 중이라면 $dp[i][j]$에 담으면 됩니다.
   $\quad$ 2-2. 뽑은 값은 제거 하고 뽑은 값을 토대로 새로운 값을 넣어줍니다. 만약에 $dp[x][y]$를 뽑았다면 $dp[x][y+1]$을, $dp[x][y] + a[x+2][i]$를 뽑았다면 $dp[x][y+1] + a[x+2][i]$을 넣어주면 됩니다.

2번 과정에서 최댓값을 뽑을 때 최대힙을 사용할 수 있습니다. 각 $dp[x]$를 구하는데 $O((n+k)\log{n})$만큼의 시간이 걸리므로 전체 시간복잡도는 $O(n(n+k)\log{n})$이 됩니다.