비용이 다른 이진 탐색 (Large)
시간 제한60초메모리 제한1536 MB
각 위치와 비교하는 비용이 주어질 때 삽입 위치를 찾는 적응적 이진 탐색의 최악 총비용 중 가장 작은 값을 구합니다.
문제
정렬된 배열에 새 원소 하나를 넣을 자리를 이진 탐색으로 찾으려 한다. 배열의 원소와 새 원소를 비교하면 "크다" 또는 "작다" 중 하나가 답으로 나온다. "크다"는 새 원소를 비교한 원소의 오른쪽에 넣어야 한다는 뜻이고, "작다"는 왼쪽에 넣어야 한다는 뜻이다. 이 문제에서 "같다"는 나오지 않는다.
비교 결과는 서로 어긋나지 않는다. 새 원소가 배열의 어떤 원소보다 크면 그 원소의 왼쪽에 있는 모든 원소보다도 크고, 어떤 원소보다 작으면 그 원소의 오른쪽에 있는 모든 원소보다도 작다. 배열의 길이가 이면 삽입할 자리는 가지다.
비교 비용은 원소마다 다르다. 배열의 번째 원소와 비교하는 데는 비용 가 들고, 는 1 이상 9 이하의 정수다.
지금까지 나온 답을 보고 다음에 비교할 원소를 정할 수 있다. 최악의 경우에 드는 비용의 합이 가장 작아지는 전략을 골랐을 때, 그 최악의 비용 합을 구하라.
입력
첫째 줄에 테스트 케이스의 개수 가 주어진다. 다음 개의 줄에는 각 테스트 케이스의 비교 비용 이 공백 없이 이어진 숫자열로 주어진다. 배열의 길이 은 이 숫자열의 길이다.
제한
- 모든 숫자는 1 이상 9 이하다.
- 한 줄 안의 숫자 사이에는 공백이 없다.
출력
각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. 는 테스트 케이스 번호이고 1부터 시작한다. 는 최악의 경우 이진 탐색에 드는 비용의 합이다.