시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 256 MB | 673 | 286 | 188 | 43.218% |
기다랗고 2N개의 방이 있는 미술관이 있다. 미술관은 세로로 N줄, 가로로 2칸의 방으로 구성된다. 위아래, 양 옆으로 붙어있는 방들은 서로 연결되어 있다. 오늘의 큐레이터는 미술관 운영진으로부터 비용 절감을 위해 k개의 방을 닫아야 한다는 통보를 받았다. 방문자들은 한쪽 끝의 두 방중 적어도 한 방에는 방문할 수 있어야 하며 다른쪽 끝의 두 방중 한 방으로 나갈 수 있어야 한다. 즉, 큐레이터는 같은 줄의 어느 두 방을 모두 닫거나 대각선으로 붙어있는 두 방을 닫아서는 안 된다는 뜻이다. 또한, 각 방들이 대중에게 공개되었을 때 얼마나 큰 가치를 지니는지를 큐레이터는 알고 있다. 큐레이터는 위 조건과 같이 방문자들의 길을 막지 않으면서 방문자들에게 공개 가능한 가치의 합을 최대로 하고 싶어한다.
그림 H.1: 샘플 인풋에 대한 최적해를 나타낸다. 회색으로 색칠된 방들을 닫아야 한다.
입력은 여러 갤러리들로 구성된다. 각각의 입력은 두 정수 N과 k(3 ≤ N ≤ 200, 0 ≤ k ≤ N)로 구성되며 각각 미술관의 세로길이와 닫아야 하는 방의 수를 뜻한다. 이어지는 N줄에 걸쳐 각 줄에 두 개의 정수가 입력되며, 각 줄에 존재하는 두 방의 가치를 뜻한다. 각 방의 가치 v는 0 이상 100 이하이다. 마지막 미술관의 정보 이후에는 두 개의 정수 0 0이 입력된다.
각 갤러리에 대해서 한 줄에 걸쳐 대중에게 공개될 수 있는 가치의 최대합을 출력한다.
6 4 3 1 2 1 1 2 1 3 3 3 0 0 0 0
17
4 3 3 4 1 1 1 1 5 6 0 0
17
10 5 7 8 4 9 3 7 5 9 7 2 10 3 0 10 3 2 6 3 7 9 0 0
102