Submission #62286414

---

Source Code Expand

package main

import (
	"bufio"
	"fmt"
	"io"
	"os"
)

func main() {
	solve(os.Stdin, os.Stdout)
}

func solve(_r io.Reader, _w io.Writer) {
	in, out := bufio.NewReader(_r), bufio.NewWriter(_w)
	defer out.Flush()

	n := readNum(in)
	s := readString(in)
	type pair struct{ x, y int }
	dp := make([][]pair, n+1)
	dp[0] = make([]pair, len(s))
	for i := 0; i < len(s); i++ {
		if s[i] == '1' {
			dp[0][i] = pair{1, 0}
		} else {
			dp[0][i] = pair{0, 1}
		}
	}

	for i := 1; i <= n; i++ {
		tmp := []pair{}
		for j := 0; j < len(dp[i-1]); j += 3 {
			tmp1 := min(dp[i-1][j].x+dp[i-1][j+1].x+dp[i-1][j+2].x, min(dp[i-1][j].x+dp[i-1][j+1].x+dp[i-1][j+2].y, min(dp[i-1][j].x+dp[i-1][j+1].y+dp[i-1][j+2].x, dp[i-1][j].y+dp[i-1][j+1].x+dp[i-1][j+2].x)))
			tmp2 := min(dp[i-1][j].y+dp[i-1][j+1].y+dp[i-1][j+2].y, min(dp[i-1][j].y+dp[i-1][j+1].y+dp[i-1][j+2].x, min(dp[i-1][j].y+dp[i-1][j+1].x+dp[i-1][j+2].y, dp[i-1][j].x+dp[i-1][j+1].y+dp[i-1][j+2].y)))
			tmp = append(tmp, pair{tmp1, tmp2})
		}
		dp[i] = tmp
	}
	fmt.Fprintln(out, dp[n][0].x+dp[n][0].y)
}

func max(a, b int) int {
	if a >= b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a <= b {
		return a
	}
	return b
}

func readString(reader *bufio.Reader) string {
	s, _ := reader.ReadString('\n')
	for i := 0; i < len(s); i++ {
		if s[i] == '\n' || s[i] == '\r' {
			return s[:i]
		}
	}
	return s
}

func readInt(bytes []byte, from int, val *int) int {
	i := from
	sign := 1
	if bytes[i] == '-' {
		sign = -1
		i++
	}
	tmp := 0
	for i < len(bytes) && bytes[i] >= '0' && bytes[i] <= '9' {
		tmp = tmp*10 + int(bytes[i]-'0')
		i++
	}
	*val = tmp * sign
	return i
}

func readNum(reader *bufio.Reader) (a int) {
	bs, _ := reader.ReadBytes('\n')
	readInt(bs, 0, &a)
	return
}

func readTwoNums(reader *bufio.Reader) (a int, b int) {
	res := readNNums(reader, 2)
	a, b = res[0], res[1]
	return
}

func readThreeNums(reader *bufio.Reader) (a int, b int, c int) {
	res := readNNums(reader, 3)
	a, b, c = res[0], res[1], res[2]
	return
}

func readNNums(reader *bufio.Reader, n int) []int {
	res := make([]int, n)
	x := 0
	bs, _ := reader.ReadBytes('\n')
	for i := 0; i < n; i++ {
		for x < len(bs) && (bs[x] < '0' || bs[x] > '9') && bs[x] != '-' {
			x++
		}
		x = readInt(bs, x, &res[i])
	}
	return res
}

Submission Info

Judge Result