Churu and his Sequence

All submissions for this problem are available.
Given a list of N numbers, say A[1..N]. And a set of integers S. Each A[i] belongs to the set S. Being said that let us first define if a array is ‘good’ or not good. We say a array, Ar[M] of size ‘M’, good if
for every pair of index (A[i] !=A[j] and 1 ≤ i, j ≤ M) there exist some index k (1 ≤ k < M) such that atleast one of the following condition hold
 Ar[k] = Ar[i] and A[k+1] = Ar[j]
 Ar[k] = Ar[j] and Ar[k+1] = Ar[i]
If it holds for every valid pair of index then we say that array Ar is good otherwise we say Ar is not good.
The given array A[N] may not be good initially and Churu want to make it good. To make the list A[N] good Churu can only do the following 
 Select an integer from the given set S.
 Then append this selected integer at the end of the list.
Churu can do these operations as many times as he wish.But appending an integer in the array is not for free. Churu has to spend some money to append an integer at the end. This amount depends on the integer that he wants to add (say e1) and the last element of the list (say it e2) after which he will append e1. Exact cost can be found from the cost matrix that will be given. Let the size of the set S be s = S. A symmetric cost matrix C[s][s] will be given. C[i][j] represents the cost of adding integer S[i] on an list if the last element of the list is S[j]. Now Churu wants to make the array good in minimum possible expenditure. Help him. Print the minimum cost to make resulting list which is good. Note that the input list, A, must be a prefix of the output list and final list and A must end with same number. Also include the initial cost to make the matrix. Assume 1st element was added free of cost.
Input
 The first line of the input contains an integer N denoting the size of A.
 Next line contains N space separated integrs denoting the initial array A.
 Next line contains single integer s denoting the size of set S.
 Next line contains s space separated integrs denoting the set S.
 All elements in S will be distinct.
 Next s lines contain s space separated integers, jth element of ith line denotes cost of appending S[i] after S[j].
 Cost matrix will be symmetric.
Output

Output a single integer denoting the minimum total cost required to make the sequence good.
Constraints
 1 ≤ N ≤ 10^{4}
 1 ≤ A[i] ≤ 10^{3}
 1 ≤ s ≤ 200
 All elements of A belong to S
 1 ≤ S[i] ≤ 10^{3} for all 1 ≤ i ≤ S
 1 ≤ c[i][j] ≤ 10^{3} for all 1 ≤ i,j ≤ S
Example
Input: 3 1 2 3 4 1 3 4 2 1 1 1 1 1 2 2 2 1 2 3 3 1 2 3 4 Output: 5
Explanation :
The optimal good sequence for the sample example will be  out[] = 1 2 3 1 3. Given sequence 1 2 3 is prefix of this sequence. Also for each valid pair of index (i, j), out[i] and out[j] occurs consecutively somewhere in the output list. Total cost = Initial cost + Additional cost = cost due of 12 + cost due to 23 + cost due to 31 + cost due to 13 = 1 + 2 + 1 + 1 = 5. First three terms are due to the initial list and rest two terms are due to additional elements appended.
Author:  triveni 
Tags  triveni 
Date Added:  10032015 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 