광인 수용소의 간수 배치
시간 제한7초메모리 제한512 MB
L개 세포를 G개 이하의 연속한 구간으로 나누는데, 길이 k인 구간은 원소마다 craziness에 k를 곱한 값을 더한다. 이때 총 비용의 최솟값을 구한다.
문제
가장 위험한 범죄자만 모아 둔 수용소의 간수 배치를 맡았다. 감방 개가 한 줄로 늘어서 있고 1번부터 번까지 번호가 붙어 있다. 번 감방에는 광기 수치가 인 수감자가 정확히 한 명 있다.
수감자 한 명마다 간수 한 명이 붙는 것이 가장 좋지만, 예산이 모자라 쓸 수 있는 간수는 명뿐이다. 탈옥 위험의 총합이 가장 작아지도록 각 간수가 감시할 수감자를 정해야 한다.
간수 한 명은 서로 이웃한 감방만 맡는다. 아무 감방도 맡지 않는 간수가 있어도 된다. 번 감방 수감자의 탈옥 위험 는 광기 수치 와 그 수감자를 맡은 간수가 감시하는 수감자 수의 곱이다. 부터 까지 를 모두 더한 값이 전체 탈옥 위험 이다.
수감자 명과 간수 명이 주어질 때 의 최솟값을 구하라.
입력
첫째 줄에 테스트 케이스의 수 가 주어진다.
각 테스트 케이스의 첫째 줄에 수감자 수 과 간수 수 가 공백으로 구분되어 주어진다. 이어지는 개 줄 가운데 번째 줄에는 번 감방 수감자의 광기 수치 가 주어진다.
제한
출력
각 테스트 케이스마다 전체 탈옥 위험 의 최솟값을 한 줄에 출력한다.