행렬 자르기
메모리 제한1024 MB
양의 정수로 채워진 N행 M열 행렬에서 가로 및 세로 자르는 순서를 정해 각 부분행렬을 자를 때 얻는 최솟값들의 합이 최대가 되도록 하고, 테스트 케이스마다 그 최댓값을 출력한다.
문제
Shekhu 교수에게는 N개의 행과 M개의 열로 이루어진 행렬이 있다. 행은 위에서 아래로 0부터 N-1까지, 열은 왼쪽에서 오른쪽으로 0부터 M-1까지 번호가 매겨진다. 행렬의 각 칸에는 양의 정수가 들어 있다.
그는 가로 방향과 세로 방향으로 자르기를 하여 이 행렬을 N * M개의 부분행렬(각각 1 * 1 크기)로 나누려고 한다. 자르기는 두 행 사이 또는 두 열 사이의 경계에서만 할 수 있다.
Shekhu 교수는 자신의 가장 뛰어난 학생인 Akki에게 이 일을 맡기며 흥미로운 제안을 한다. Akki가 어떤 부분행렬에서 자르기를 할 때마다, 자르기 전에 그 부분행렬의 최솟값만큼의 동전을 받는다. 자르기를 할 때마다 전체 부분행렬의 수가 늘어난다. 또한 서로 다른 두 부분행렬에서의 자르기는 서로 독립적이며, 마찬가지로 Akki는 서로 다른 부분행렬에서의 자르기에 대해 독립적으로 동전을 받는다.
Akki는 여러 가지 방법으로 자르기를 할 수 있다. 그가 받을 수 있는 동전의 총 개수를 최대로 하려면 어떻게 해야 하는지 구해 주자.
입력
입력의 첫 줄에는 정수 T가 주어지며, 이는 테스트 케이스의 수이다. 이어서 T개의 테스트 케이스가 따른다. 각 테스트 케이스의 첫 줄에는 위에서 설명한 대로 두 정수 N과 M이 주어진다.
- 다음으로 N개의 줄에 각각 M개의 양의 정수가 주어지며, 이는 행렬을 나타낸다.
출력
각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 Akki가 최적의 순서로 자르기를 했을 때 받을 수 있는 최대 동전 개수이다.
제한
- 1 ≤ T ≤ 100.
- 1 ≤ 행렬의 각 값 ≤ 105.
힌트
예제 1에서 Akki가 자르기를 할 수 있는 방법은 두 가지이다.
- Akki가 먼저 행렬을 가로로 자른다고 하자. 그러면 행렬의 최솟값인 1을 받는다. 그 다음 두 부분행렬(([1, 2])와 ([3, 4]))에서 세로로 잘라야 하며, 각각 1과 3개의 동전을 받는다.
- Akki가 먼저 행렬을 세로로 자른다고 하자. 그러면 행렬의 최솟값인 1을 받는다. 그 다음 두 부분행렬(전치하면 ([1, 3])과 ([2, 4]))에서 가로로 잘라야 하며, 각각 1과 2개의 동전을 받는다.
첫 번째 방법이 더 좋으며, 답은 5이다.
예제 2에서 Akki는 최대 7개의 동전을 받을 수 있다. 최적의 방법 중 하나는 먼저 유일한 가로 자르기를 하여 1개의 동전을 받는 것이다. 그 다음 위쪽 부분행렬 ([1, 2, 1])에서 첫 번째 열 바로 오른쪽을 자르고, 이어서 두 번째 열 바로 오른쪽을 잘라 총 2개의 동전을 받는다. 마찬가지로 아래쪽 부분행렬 ([2, 3, 2])에서 두 번째 열 바로 오른쪽을 자르고, 이어서 첫 번째 열 바로 오른쪽을 잘라 총 4개의 동전을 받는다.
예제 3에서는 자를 곳이 한 군데뿐이다.