시간 제한 메모리 제한 제출 횟수 정답 횟수 (비율) 정답자 수
2.0 초 256 MB (%)
문제
당신은 스택에 있는 N개의 디스크(1<=N<=100)를 가지고 게임을 할 것이다. 게임의 목적은 스택안의 모든 디스크를 없애는 것이다. 하지만, 디스크를 없앨때 비용이 필요하고, 당신의 목적은 모든 디스크를 없앨 때 비용을 최소화하는 것이다. 각각 디스크는 Label을 가지고 있다. Label L의 범위는 1<=L<=20이다. 당신은 또한 당신의 스택에서 디스크를 없앨 때 도움을 줄 "마스터 스택"을 갖고있다. 당신의 스택에서 디스크를 없앨때 다음 두가지 방법이 있다: 1. 당신의 스택의 맨위에있는 디스크를 없앤다: 만약 맨위에 있는 디스크의 Label이 c라면, 이것을 없앨 때 비용이 c가 발생한다. 2. 당신의 스택의 맨위에 있는 디스크와 마스터스택의 맨위에 있는 디스크의 Label이 같다면 동시에 없앤다: 이 경우, 두 디스크들을 없앨 때 비용이 들지 않는다. 당신은 또한 당신의 스택에 위의 K개를 변경할 수 있다. 각 변경 직후에, 당신의 스택의 맨위의 원소를 제거한다. 여기에 세 종류의 변경이 있다: 1. 뒤집기 : 당신의 스택에서 맨위의 r개를 뒤집는다.(2<=r<=K) 다시말해, 만약 맨위 r개의 디스크가 d1, d2, ..., dr(위에서부터 아래로 읽었을때)이라면, 이 연산을 하고 나면 맨위 r개의 디스크는 dr, ..., d2, d1 (위에서부터 아래로 읽었을때)가 된다. 이것의 비용은 R이다. (1<=R<=1,000,000) 2. (환형 shift) 위로 : 당신은 맨위 u개의 디스크를 위 방향으로 shift할 수 있다. (2<=u<=K). 예를들어, 만약 맨위의 디스크 4개를 d1, d2, d3, d4 (위에서 아래로 읽었을 때) 라고 하면 위로 shift연산을 세개에 대해 적용할 경우 d2,d3,d1,d4가 되며, 네개에 대해 적용하면 d2,d3,d4,d1가 된다. 이 위로 shift연산의 비용은 U이다. (1<=U<=1,000,000) 3. (환형 shift) 아래로 : 당신은 맨위에서 d개를 선택해 아래 방향으로 shift할 수 있다. (2<=d<=K). 예를들어, 만약 맨위의 디스크 4개를 d1, d2, d3, d4라 하자. 만약 맨위 3개에 아래로 shift연산을 사용하면 d3, d1, d2, d4가 되며, 네개에 대해 적용하면 d4, d1, d2, d3가 된다. 이 아래로 shfit연산의 비용은 D이다. (1<=D<=1,000,000) 만약 연산의 결과 마스터 스택과 당신의 스택의 맨위가 같아지면, 공짜로 제거할 수 있다. 만약 아니면, 당신은 무조건 제거비용을 지불하게 된다. 한가지 추가적인 제한이 있다. 게임의 언제라도, 레벨 j의 디스크를 제거할 때 (레벨은 맨 아래를 0으로 본다), 원래 처음의 레벨이 j+M이거나 더 높은 디스크들은 이미 제거되었어야 한다. 1<= M <=5. 스택내 모든 디스크를 제거하는데 드는 비용을 최소화하라.
입력
첫 줄에 6개의 정수가 공백으로 구분되어 주어진다: N, K, M, D, U, R 의 의미는: - N는 각 스택의 디스그의 갯수이다. (1<=N<=100) - K, 각 오퍼레이션의 최대 결정 깊이이다. (1<=K<=4) - M, 디스크를 지우기 전에 경계조건이다. (1<=M<=5) - D, 아래로 shift의 비용이다. (1<=D<=1000000) - U, 위로 shift의 비용이다. (1<=U<=1000000) - R, 뒤집기의 비용이다. (1<=R<=1000000) 다음 2N줄에 걸쳐서, 각 줄에는 숫자 L이 주어진다. (1<=L<=20) 처음 N개의 줄은 마스터 스택의 디스크들의 라벨이, 위에서 아래 순서로 주어진다. 그 다음 N개의 줄은 당신의 스택에 있는 디스크들의 라벨이며, 위에서 아래 순서로 주어진다. Note : 20%의 채점 데이터는 K<=2라 가정해도 좋다.
출력
한줄에 디스크를 모두 제거하는데 드는 최소비용을 출력한다.
힌트
입력예제 ``` 7 3 3 4 4 3 5 6 3 5 4 1 2 3 5 6 5 1 4 1 ``` 출력예제 ``` 5 ``` 예제설명 위에서 3개를 잡아 shift 위로 연산을 비용 4를 이용해 하면, 4개의 디스크를 공짜로 지울 수 있다. 그 뒤 1의 비용으로 라벨 1인 디스크를 지우면, 나머지는 다시 공짜로 지울 수 있게 된다.