Link

题意

见题链。

思路

赛后看了一眼这个题解，自己写出来了。赛中没有写出来

代码

package main

func minimumCost(s string) int64 {
	n := len(s)
	dp1 := make([][]int64, n+1)
	for i := range dp1 {
		dp1[i] = make([]int64, 2)
	}
	dp2 := make([][]int64, n+1)
	for i := range dp2 {
		dp2[i] = make([]int64, 2)
	}
	lastOneIdx, lastZeroIdx := -1, -1
	for i := 0; i < n; i++ {
		if s[i] == '1' {
			dp1[i+1][1] = dp1[i][1]
			dp1[i+1][0] = dp1[lastZeroIdx+1][1] + int64(i+1)
			lastOneIdx = i
		} else {
			dp1[i+1][0] = dp1[i][0]
			dp1[i+1][1] = dp1[lastOneIdx+1][0] + int64(i+1)
			lastZeroIdx = i
		}
	}
	lastOneIdx, lastZeroIdx = n, n
	for i := n - 1; i >= 0; i-- {
		if s[i] == '1' {
			dp2[i][1] = dp2[i+1][1]
			dp2[i][0] = dp2[lastZeroIdx][1] + int64(n-i)
			lastOneIdx = i
		} else {
			dp2[i][0] = dp2[i+1][0]
			dp2[i][1] = dp2[lastOneIdx][0] + int64(n-i)
			lastZeroIdx = i
		}
	}
	ans := int64(2e18)
	for i := 0; i < n; i++ {
		ans = min(ans, dp1[i+1][0]+dp2[i+1][0])
		ans = min(ans, dp1[i+1][1]+dp2[i+1][1])
	}
	return ans
}

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