Optimal BST Revisited

All submissions for this problem are available.
A rooted binary tree is a rooted tree such that each node has atmost 2 children. A Binary Search Tree (BST) is a rooted binary tree, which has values stored in each of its nodes. We are interested only in distinct values. A BST has to satisfy the property that, for every node, its value must be greater than the value of every node on its left subtree, if it exists. Also, for every node, its value must be lesser than the value of every node on its right subtree, if it exists.
Thunk is bored with the classical problem of finding an optimal BST. He decides to spice it up, and changes the cost function. The problem he is considering is as follows: Given a BST with N nodes, called T, which store the values {1,2,..,N}, and a sequence of Searches S = (s_{1}, s_{2}, ..., s_{m}), he puts his finger on the root of T, and then traces the path to the node containing s_{1}, and then from there, to the node containing s_{2}, ..., and he finally traces the path from s_{m1} to s_{m}. Note that during this process, he might have passed through, or even searched for the same element/node multiple times, if the Search sequence was so given. And he defines the Cost to be the total distance (or the number of edges) that he has passed through.
Formally, Cost(T,S) = Depth(s_{1}) + Distance(s_{1}, s_{2}) + Distance(s_{2}, s_{3}) + ... + Distance(s_{m1}, s_{m}).
Depth(u) is defined to be the number of edges on the unique path from the root of the BST to the node conatining the value u. Distance(u,v) is defined to be the number of edges on the unique path from the node containing the value u to the node containing the value v.
Thunk has to hurry to finish his The Art of Competitive Programming series of books, and so doesn't want to waste too much time on this. So, given the sequence of Searches, S = (s_{1}, s_{2}, ..., s_{m}), help him find the minimum Cost, over all valid BSTs on {1,2,..,N}. That is, find the minimum of Cost(T,S), over all valid Ts.
Input
The first line contains two integers N, M, denoting the number of nodes to be present in the BST, and the length of the search sequence S.
The next line contains M integers ,separated by single spaces: s_{1}, s_{2}, .., s_{M}, denoting search sequence S.
Output
Output a single line containing the answer, which is the minimum Cost over all valid BSTs.
Constraints
 1 ≤ N ≤ 500
 1 ≤ M ≤ 10^{6}
 1 ≤ S_{i} ≤ N
Example
Input: 3 5 1 3 2 1 2 Output: 5
Explanation
For N = 3, there are 5 valid BSTs possible:T_{1}: 2 / \ 1 3 T_{2}: 1 \ 2 \ 3 T_{3}: 3 / 2 / 1 T_{4}: 1 \ 3 / 2 T_{5}: 3 / 1 \ 2 S = (1, 3, 2, 1, 2) Cost(T_{1}, S) = Depth(1) + Distance(1, 3) + Distance(3, 2) + Distance(2, 1) + Distance(1, 2) = 1 + 2 + 1 + 1 + 1 = 6 Cost(T_{2}, S) = Depth(1) + Distance(1, 3) + Distance(3, 2) + Distance(2, 1) + Distance(1, 2) = 0 + 2 + 1 + 1 + 1 = 5 Cost(T_{3}, S) = Depth(1) + Distance(1, 3) + Distance(3, 2) + Distance(2, 1) + Distance(1, 2) = 2 + 2 + 1 + 1 + 1 = 7 Cost(T_{4}, S) = Depth(1) + Distance(1, 3) + Distance(3, 2) + Distance(2, 1) + Distance(1, 2) = 0 + 1 + 1 + 2 + 2 = 6 Cost(T_{5}, S) = Depth(1) + Distance(1, 3) + Distance(3, 2) + Distance(2, 1) + Distance(1, 2) = 1 + 1 + 2 + 1 + 1 = 6We see that the minimum Cost is attained by T_{2}, and it is 5. Hence the answer is 5.
Author:  admin2 
Editorial  https://discuss.codechef.com/problems/KOL16L 
Tags  acm16kol, admin2, dynamicprogramming, medium 
Date Added:  26122016 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYP3 
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. 