AcWing 282. 石子合并-go
原题链接
简单
作者:
一只鱼
,
2022-04-21 20:03:56
,
所有人可见
,
阅读 125
AcWing 282. 石子合并-go
package main
import(
"fmt"
)
const maxLen = 300+10
var(
N int
w [maxLen]int
f [maxLen][maxLen]int
)
func main(){
fmt.Scan(&N)
for i := 1; i <= N; i++{
fmt.Scan(&w[i])
w[i] += w[i-1]
}
for length := 2; length <= N; length++{
for l := 1; l + length -1 <= N; l++{
r := l+length-1
f[l][r] = 1e8
for k := l; k < r; k++{
f[l][r] = min(f[l][r], f[l][k] + f[k+1][r] + w[r] - w[l-1])
}
}
}
fmt.Println(f[1][N])
}
func min(a, b int)int{
if a <= b{
return a
}
return b
}