당신은 정해진 역도 훈련 프로그램을 따르고 있다. 이 훈련은 순서대로 수행해야 하는 일련의 운동(exercise)들로 이루어져 있다. 각 운동은 기계에 특정한 구성의 무게추를 올려야 한다.

무게추의 종류는 서로 다른 \mathbf{W}가지가 있다. 예를 들어 어떤 운동은 A 타입 무게추 3개와 B 타입 무게추 1개가 필요하고, 다음 운동은 A, C, D 타입 무게추가 각각 2개씩 필요할 수 있다.

Weightlifting example.

무게추들은 기계 위에 스택(stack) 형태로 쌓인다. 형식적으로, 한 번의 연산으로 임의의 타입의 무게추 하나를 스택의 맨 위에 올리거나, 현재 스택의 맨 위에 있는 무게추 하나를 제거할 수 있다.

각 운동에 필요한 무게추들을 스택에 올리는 순서는 당신이 마음대로 정할 수 있다. 따라서 위 예시에서 첫 번째 운동에서 B 타입 무게추를 맨 아래에 두면, 두 번째 운동을 위해 모든 무게추를 다 빼고 다시 올려야 한다. 반면 B 타입 무게추를 아래에서 세 번째 위치에 두면, A 타입 무게추 2개를 스택의 아래쪽에 그대로 남겨 다음 운동의 무게추 구성에 포함시킬 수 있어 시간을 절약할 수 있다.

각 운동마다 각 타입의 무게추가 몇 개 필요한지가 주어질 때, 모든 운동을 수행하기 위해 필요한 연산 횟수의 최소를 구하라. 운동은 주어진 순서대로 완료해야 한다. 기계의 스택은 처음에 비어 있고, 모든 운동을 끝냈을 때도 스택을 비워 둬야 한다.

#10428 upload 2 done 2 how_to_reg 2

역도 timer 20s memory 1024MB

#10428

역도 20s 1024MB