GCJ/2008/2/D/main.go

package main

import (
	"fmt"
)

func main() {
	var N, k int
	fmt.Scan(&N)
	for cid := 0; cid < N; cid++ {
		fmt.Scan(&k)
		var S string
		fmt.Scan(&S)
		n := len(S)
		// edge[x][y] means the weight of edge: x -> y
		// init[x][y] means the weight of edge: init point x -> y
		edge, init := make([][]int, k), make([][]int, k)
		for i := 0; i < k; i++ {
			edge[i], init[i] = make([]int, k), make([]int, k)
		}
		for x := 0; x < k; x++ {
			for y := 0; y < k; y++ {
				if x != y {
					for o := 0; o < n; o += k {
						if S[o+x] != S[o+y] {
							edge[x][y]++
						}
					}
					for o := 0; o < n-k; o += k {
						if S[o+x] != S[o+k+y] {
							init[x][y]++
						}
					} // Note: y -> x and x -> y is NOT THE SAME INIT edge!!!
				}
			}
		}
		dp := make([][]int, 1<<uint(k))
		for i := range dp {
			dp[i] = make([]int, k)
		}
		const inf = 1000000
		ans := inf
		for beg := 0; beg < k; beg++ {
			for i := range dp {
				for j := range dp[i] {
					dp[i][j] = inf
				}
			}
			dp[1<<uint(beg)][beg] = 1
			for mask := 0; mask < (1 << uint(k)); mask++ {
				for i := 0; i < k; i++ {
					if dp[mask][i] < inf {
						for j := 0; j < k; j++ {
							newset := mask | (1 << uint(j))
							if newset != mask {
								dp[newset][j] = minInt(dp[newset][j], dp[mask][i]+edge[i][j])
							}
						}
					}
				}
			}
			for i := 0; i < k; i++ {
				ans = minInt(ans, dp[(1<<uint(k))-1][i]+init[i][beg])
			}
		}
		fmt.Printf("Case #%d: %d\n", cid+1, ans)
	}
}