이어달리기
시간 제한2초메모리 제한128 MB
고정된 순서의 N명 주자가 각각 1~3일씩 뛰어 총 D일을 채우도록 배정해 총 거리를 최대화하고, 불가능하면 -1을 출력합니다.
- 난이도
보통10점 중 5점
- 유형
- 동적 계획법
- 정답자
- 아직 제출이 없습니다
문제
한 팀은 정해진 순서로 N명의 선수를 이어 달리게 한다. 대회는 D일 동안 진행되며, 매일 한 명의 선수만 달린다.
선수 교체는 하루가 시작될 때에만 할 수 있다. 한 번 다음 선수로 넘어가면 이전 선수는 다시 달릴 수 없다. 모든 선수는 정해진 순서대로 정확히 한 번 참가해야 하며, 각 선수는 연속으로 최소 1일, 최대 3일을 달려야 한다.
각 선수에게는 세 개의 기록 (a, b, c)가 주어진다. 이 값은 그 선수가 각각 1일, 2일, 3일 연속으로 달렸을 때 갈 수 있는 거리이다. 모든 올바른 기록은 a <= b <= c를 만족해야 한다.
N명의 선수 순서는 이미 정해져 있다. 각 선수가 며칠씩 달릴지를 정해, 정확히 D일 동안 갈 수 있는 총거리의 최댓값을 구하라.
입력
첫 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스는 다음과 같이 주어진다.
- 첫 줄에 선수 수 N이 주어진다.
(1 <= N <= 50) - 다음 줄에 대회 기간 D가 주어진다.
(1 <= D <= 150) - 이어지는 N개의 줄에는 선수가 출전하는 순서대로 각 선수의 기록
a b c가 주어진다.
각 기록은 1일, 2일, 3일 연속으로 달렸을 때의 거리이다.
출력
각 테스트 케이스마다 한 줄에 하나의 정수를 출력한다.
정확히 D일 동안 달릴 수 있는 총거리의 최댓값을 출력한다. 기록이 올바르지 않거나 규칙을 만족하도록 선수를 배정할 수 없다면 -1을 출력한다.