Go 代码

package main

import "fmt"

const N = 305
var n int
var s [N]int
var f [N][N]int

func main() {
    fmt.Scan(&n)
    for i := 1; i <= n; i++ {
        fmt.Scan(&s[i])
        s[i] += s[i-1]
    }

    for len := 2; len <= n; len++ {
        for i := 1; i + len - 1 <= n; i++ {
            j := i + len - 1
            f[i][j] = int(^uint(0) >> 1)
            for k := i; k < j; k++ {
                f[i][j] = min(f[i][j], f[i][k] + f[k+1][j] + s[j] - s[i-1])
            }
        }
    }

    fmt.Println(f[1][n])
}

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