레이팅 미적용베시는 인기 격투 게임 Moortal Cowmbat을 오랫동안 즐겨 왔다. 하지만 최근 게임 개발자들이 업데이트를 배포하면서 베시는 플레이 스타일을 바꿔야만 하게 되었다.
이 게임은 처음 \(M\)개의 소문자 알파벳으로 표시된 \(M\)개의 버튼을 사용한다(\(1 \leq M \leq 26\)). 게임에서 베시가 가장 좋아하는 콤보는 버튼 입력들로 이루어진 길이 \(N\)의 문자열 \(S\)이다(\(1 \leq N \leq 10^5\)). 그런데 최근 업데이트로 인해, 이제 모든 콤보는 일련의 "연타(streak)"들로 구성되어야 한다. 연타란 같은 버튼을 연속으로 \(K\)번 이상 누른 구간을 말한다(\(1 \leq K \leq N\)). 베시는 자신이 가장 좋아하는 콤보를 수정하여, 길이는 같은 \(N\)이지만 규칙 변경을 만족하도록 버튼 입력의 연타들로 이루어진 새 콤보를 만들고 싶다.
베시가 콤보의 어떤 특정 위치에서 버튼 \(i\) 대신 버튼 \(j\)를 누르도록 훈련하는 데는 \(a_{ij}\)일이 걸린다(즉, \(S\)의 특정 문자 하나를 \(i\)에서 \(j\)로 바꾸는 데 \(a_{ij}\)의 비용이 든다). 버튼 \(i\)에서 중간 버튼 \(k\)로 바꾼 뒤 버튼 \(k\)에서 버튼 \(j\)로 바꾸는 것이 \(i\)에서 \(j\)로 직접 바꾸는 것보다 시간이 덜 걸릴 수도 있음에 유의하라(더 일반적으로, \(i\)에서 시작해 \(j\)로 끝나는 변경 경로가 버튼 \(i\)를 최종적으로 버튼 \(j\)로 바꾸는 최적의 전체 비용을 줄 수도 있다).
베시가 새 요구 사항을 만족하는 콤보를 만드는 데 필요한 최소 일수를 구하도록 도와주자.
문제 제공: Eric Wei
점수 배점
- 테스트 케이스 2-4는 \(N\le 1000, K\le 50\)을 만족한다.
- 테스트 케이스 5-8은 \(N\le 30,000, K\le 50\)을 만족한다.
문제 제공: Eric Wei
첫째 줄에 \(N\), \(M\), \(K\)가 주어진다. 둘째 줄에 \(S\)가 주어지고, 마지막 \(M\)개의 줄에 값 \(a_{ij}\)로 이루어진 \(M\times M\) 행렬이 주어진다. 여기서 \(a_{ij}\)는 \(0 \ldots 1000\) 범위의 정수이며, 모든 \(i\)에 대해 \(a_{ii} = 0\)이다.
베시가 콤보를 새 요구 사항을 만족하는 것으로 바꾸는 데 필요한 최소 일수를 나타내는 수 하나를 출력한다.
cowmbat.in · 출력을 쓸 파일 cowmbat.out5 5 2
abcde
0 1 4 4 4
2 0 4 4 4
6 5 0 3 2
5 5 5 0 4
3 7 0 5 05The optimal solution in this example is to change the a into b, change the d into e, and then
change both e’s into c’s. This will take \(1+4+0+0=5\) days, and the final
combo string will be bbccc.
riseoj 작성
출처 올림피아드 > USACO > 2019-2020 > December > Gold