题解 | #合唱队#

package main import ( "fmt" )

func main() { var n int var dp []int for { _, err := fmt.Scan(&n) if err != nil { break } dp = make([]int, n) for i := 0; i < n; i++ { fmt.Scan(&dp[i]) } fmt.Println(hechangdui(dp)) } }

func hechangdui(s []int) int { dp1, dp2 := make([]int, len(s)), make([]int, len(s)) for i := 1; i < len(s); i++ { for j := 0; j < i; j++{ if s[i] > s[j] && dp1[i] < dp1[j]+1 { dp1[i] = dp1[j]+1 } } } for i := len(s)-2; i >= 0; i-- { for j := len(s)-1; j > i; j--{ if s[i] > s[j] && dp2[i] < dp2[j]+1 { dp2[i] = dp2[j]+1 } } } max := 1 for i := 0; i < len(s); i++ { if max < dp1[i]+dp2[i]+1 { max = dp1[i]+dp2[i]+1 } } return len(s)-max

}