package main import . "fmt" import "math/rand" func main() { var n,q int Scan(&n,&q) a := make([]int, n) for i := range a { Scan(&a[i]) } b := make([]int, q) for i := range b { Scan(&b[i]) } ans := neighbour(n, q, a, b) Println(ans) } func solve(n, q int, a, b []int) int { m := make(map[int][]int) for i, x := range a { m[x] = append(m[x], i) } dp := make([][]int, q+1) for i := range dp { dp[i] = make([]int, n) for j := range dp[i] { dp[i][j] = 1e15 } } dp[0][0] = 0 cur := []int{0} for i, x := range b { if a[cur[0]] == x { dp[i+1] = dp[i] continue } next := m[x] for _, from := range cur { cost := dp[i][from] for _, to := range next { dp[i+1][to] = min(dp[i+1][to], cost+abs(from-to)) } } cur = next } var ans int = 1e15 for _, i := range cur { ans = min(ans, dp[q][i]) } return ans } func abs(x int) int { if x < 0 { return -x } else { return x } } func init() { // check() } func check() { rand.Perm(1000) println(rand.Intn(1000)) n, q := 1000, 1000 a := make([]int, n) b := make([]int, q) for ee := 0; ee < 100; ee++ { for i := range a { a[i] = rand.Intn(500)+1 } for i := range b { b[i] = a[rand.Intn(len(a))] } a1 := solve(n, q, a, b) a2 := neighbour(n, q, a, b) if a1 != a2 { println("not equal") println(n, q) println(a) println(b) return } } } func neighbour(n, q int, a, b []int) int { cur := make([]int, n) for i := range cur[1:] { cur[i+1]=1e15 } tmp := make([]int, n) for _, x := range b { for i := range tmp { tmp[i] = 1e15 } for p, c := range cur { if c == 1e15 { continue } for i:=p; i < n; i++ { if a[i] == x { tmp[i] = min(tmp[i], c+abs(p-i)) break } } for i:=p-1; i >= 0; i-- { if a[i] == x { tmp[i] = min(tmp[i], c+abs(p-i)) break } } } cur, tmp = tmp, cur } ans := int(1e15) for _, c := range cur { ans = min(ans, c) } return ans }