#PU971. USACO 2019 December Contest, Gold — Problem 3. Moortal Cowmbat
USACO 2019 December Contest, Gold — Problem 3. Moortal Cowmbat
USACO 2019 December Contest, Gold — Problem 3. Moortal Cowmbat
题目描述
Bessie has been playing the popular fighting game Moortal Cowmbat for a long time now. However, the game developers have recently rolled out an update that is forcing Bessie to change her play style. The game uses buttons labeled by the first lowercase letters (). Bessie's favorite combo of moves in the game is a length- string of button presses (). However, due to the most recent update, every combo must now be made from a series of "streaks", where a streak is defined as a series of the same button pressed at least times in a row (). Bessie wants to modify her favorite combo to produce a new combo of the same length , but made from streaks of button presses to satisfy the change in rules. It takes days for Bessie to train herself to press button instead of button at any specific location in her combo (i.e. it costs to change a single specific letter in from to ). Note that it might take less time to switch from using button to an intermediate button and then from button to button rather than from to directly (or more generally, there may be a path of changes starting with and ending with that gives the best overall cost for switching from button ultimately to button ). Help Bessie determine the smallest possible number of days she needs to create a combo that supports the new requirements.
输入格式
The first line of input contains , , and . The second line contains , and the final lines contain an matrix of values , where is an integer in the range and for all .
输出格式
(见题面原文)
数据范围
Test cases 2-4 satisfy Test cases 5-8 satisfy
样例
样例 1
5 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 0
5
The 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.
Problem credits: Eric Wei