Min Cost String :
Difficulty Level : Medium
Submissions : 426
Asked In :
Marks :15
: 3 | : 0
Consider an alphabet system containing only 4 characters. You are given a matrix $$$cost$$$ of size $$$n \times 4$$$ where $$$cost[i][j]$$$ denotes the cost of placing the $$$j-th$$$ character at the $$$i-th$$$ position.
Find the minimum cost to create a string of length $$$n$$$ such that no two consecutive characters are same.
The first line of input contains an integer $$$t \hspace{2pt} (1 \le t \le 10^4)$$$ — the number of testcases. The description of $$$t$$$ testcases follows.
The first line of each testcase contains an integer $$$n \hspace{2pt} (1 \le n \le 10^5)$$$ — the length of string required.
The next $$$n$$$ lines contain $$$4$$$ integers each denoting the $$$cost$$$ matrix. $$$(0 \le cost[i][j] \le 1000)$$$.
It is guaranteed that the sum of $$$n$$$ over all testcases does not exceed $$$10^5.$$$
For each testcase, print the minimum cost of creating a string of length $$$n$$$ in a single line.
1 4 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
30
In the sample testcase, One of the optimal ways is to use the 1st and 2nd characters alternatively (either "1212" or "2121") for a total cost of 30.
