벽화
면접 대비시간 제한20초메모리 제한1024 MB
벽의 미적 점수를 나타내는 숫자 문자열이 주어질 때, 매일 이미 칠한 구간에 인접한 칸을 칠하고 칠하지 않은 끝 칸 하나가 무너지는 상황에서 탄이가 보장할 수 있는 최대 미적 총합을 구한다.
문제
Thanh는 길이가 N인 벽에 멋진 벽화를 그리려고 한다. 벽의 각 구역에는 미적 점수가 있어서, 그 구역을 칠했을 때 얼마나 아름다운지 나타낸다. 그런데 최근 홍수로 벽이 무너지기 시작했으므로 Thanh는 서둘러야 한다.
매일 아침 Thanh는 벽의 한 구역을 칠한다. 첫째 날에는 원하는 구역을 마음대로 칠할 수 있다. 그 이후의 날에는 벽화가 끊기지 않아야 하므로, 이미 칠한 구역에 인접한 새 구역을 칠해야 한다.
매일 저녁 벽의 한 구역이 무너진다. 이때 무너지는 구역은 항상 다른 구역 하나와만 인접하고 아직 칠하지 않은 구역이다. Thanh는 방수 페인트를 사용하므로 칠한 구역은 무너지지 않는다.
벽화의 총 미적 점수는 Thanh가 칠한 구역들의 미적 점수를 모두 더한 값이다. Thanh는 벽이 어떻게 무너지더라도 총 미적 점수를 B 이상으로 만들 수 있음을 보장하고 싶다. 그가 보장할 수 있는 B의 최댓값은 얼마인가?
입력
입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. T개의 테스트 케이스가 이어진다. 각 테스트 케이스의 첫 줄에는 정수 N이 주어진다. 그다음 줄에는 0부터 9까지의 숫자 N개로 이루어진 문자열이 주어진다. i번째 숫자는 벽의 i번째 구역의 미적 점수이다.
출력
각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 위에서 설명한 대로 Thanh가 달성할 수 있음을 보장하는 최대 미적 점수이다.
제한
- 1 ≤ T ≤ 100.
힌트
첫 번째 예시에서 Thanh는 벽이 어떻게 무너지더라도 총 미적 점수 6을 얻을 수 있다. 첫째 날에는 미적 점수가 3인 두 구역 중 아무 곳이나 칠할 수 있다. 그날 저녁에 1번째 구역이나 4번째 구역 중 하나가 무너지지만 어느 쪽이든 상관없다. 둘째 날에는 미적 점수가 3인 나머지 구역을 칠할 수 있다.
두 번째 예시에서 Thanh는 가장 왼쪽 구역(미적 점수 9)을 칠해서 총 미적 점수 14를 얻을 수 있다. 가장 왼쪽 구역은 칠해져 있으므로 무너질 수 있는 구역은 가장 오른쪽 구역뿐이다. 둘째 날에는 왼쪽에서 두 번째 구역(미적 점수 5)을 칠할 수 있다. 그러면 오른쪽에 남은 마지막 칠하지 않은 구역이 무너진다. 둘째 날에 Thanh가 3번째 구역(미적 점수 8)을 칠할 수는 없다. 이 구역은 칠한 구역과 인접하지 않기 때문이다.
세 번째 예시에서 Thanh는 총 미적 점수 7을 얻을 수 있다. 가운데 구역(미적 점수 1)을 칠하는 것으로 시작한다. 그날 저녁 어느 구역이 무너지더라도 둘째 날 아침에 남은 벽을 칠할 수 있다.