Go: package main

import (
	"fmt"
	"math"
)

func main() {
	var n int
	fmt.Scan(&n)

	p := make([]float64, n+1)
	q := make([]float64, n+1)
	psum := make([]float64, n+2) // i番目はi-1までの和とする
	qsum := make([]float64, n+2) // i番目はi-1までの和とする
	for i := 1; i <= n; i++ {
		fmt.Scan(&p[i])
		psum[i+1] = psum[i] + p[i]
	}
	for i := 0; i <= n; i++ {
		fmt.Scan(&q[i])
		qsum[i+1] = qsum[i] + q[i]
	}

	dp := make([][]float64, n+1)
	for i := 0; i <= n; i++ {
		dp[i] = make([]float64, n+1)
	}

	// calc
	for d := 0; d <= n; d++ {
		for l := 0; l+d <= n; l++ {
			r := l+d
			if l == r {
				dp[l][r] = q[l]
				continue
			}

			dp[l][r] = 1 << 30
			// iは中心となるnode
			for i := l+1; i <= r; i++ {
				left := dp[l][i-1] + psum[i] - psum[l+1] + qsum[i] - qsum[l]
				right := dp[i][r] + psum[r+1] - psum[i+1] + qsum[r+1] - qsum[i]
				dp[l][r] = math.Min(dp[l][r], p[i] + left + right)
			}
		}
	}

	fmt.Printf("%.8f\n", dp[0][n])
}

Python: n=int(input())
p=[float(i) for i in input().split()]
q=[float(i) for i in input().split()]
pq = [q[-1]]*2*(n+1)
dp = {}
for i in range(n):
    pq[2*i+1] = q[i]
    pq[2*i+2] = p[i]
for i in range(len(pq)):
    for j in range(len(pq)-i):
        if i == 0:
            dp[(j,j+i)] = 0
        elif i == 1:
            dp[(j,j+i)] = pq[j+i]
        else:
            tmp = 1001
            for k in range(i):
                c = dp[(j,j+k)] + dp[(j+k+1,j+i)]+sum(pq[j+1:j+i+1])
                if c < tmp:
                    tmp = c
            dp[(j,j+i)] = tmp
print(dp[(0,2*n+1)])

Python: import sys

n = int(sys.stdin.readline())
a = [0.0] * (2*n+1)
b = list(map(float, sys.stdin.readline().split()))
for i,c in enumerate(b):    a[i*2+1] = c
b = list(map(float, sys.stdin.readline().split()))
for i,c in enumerate(b):    a[i*2] = c
depth = [0]*(n*2+1)
ans = max(a)*(n*2+1)*n
def walk(d, s, e):
    global ans
    if s>=e:
        depth[s*2+1]=d
        er = 0
        for i in range(0,n*2+1,2):
            if i==0:      depth[i]=depth[i+1]+1
            elif i==n*2:  depth[i]=depth[i-1]+1
            else:         depth[i]=max(depth[i-1],depth[i+1])+1
        for i in range(n*2+1):
            er += (depth[i]+1)*a[i]
        if ans>er: ans = er
        return
    for m in range(s, e+1):
        depth[m*2+1]=d
        if s<=m-1:  walk(d+1,  s, m-1)
        if m+1<=e:  walk(d+1, m+1, e)
        
walk(0, 0, n-1)
print(ans)

Python: import sys
readline = sys.stdin.readline
write = sys.stdout.write

N = int(readline())
*P, = map(float, readline().split())
*Q, = map(float, readline().split())

K = [[None]*(N+1) for i in range(N+1)]
C = [[None]*(N+1) for i in range(N+1)]
S = [0]*(2*N+2)
for i in range(2*N+1):
    S[i+1] = S[i] + (P[i//2] if i % 2 else Q[i//2])

for i in range(N+1):
    C[i][i] = Q[i]
    K[i][i] = i

for l in range(1, N+1):
    for i in range(N+1-l):
        j = i+l
        k0 = K[i][j-1]; k1 = K[i+1][j]
        tmp = 1e30
        k2 = None
        for k in range(k0, min(k1+1, j)):
            v = C[i][k] + C[k+1][j]
            if v < tmp:
                k2 = k
                tmp = v
        K[i][j] = k2
        C[i][j] = tmp + (S[2*j+1] - S[2*i])
write("%.10f\n" % C[0][N])

Python: import sys

n = int(sys.stdin.readline())

ky = list(map(float, sys.stdin.readline().split()))
dm = list(map(float, sys.stdin.readline().split()))
depth = [0]*n
ans = max(max(ky),max(dm))*(n*2+1)*(n+1)

def traverse(d, s, e, note):
    global ans
    if s==e:
        depth[s]=d
        er = 0

        for i in range(n):         er += depth[i]*ky[i]
        er += (depth[0]+1)*dm[0]
        for i in range(1, n):      er += (max(depth[i-1], depth[i])+1)*dm[i]
        er += (depth[n-1]+1)*dm[n]
        
        if ans>er: ans = er
        return
    for m in range(s, e+1):
        depth[m]=d
        if s<=m-1: traverse(d+1,  s, m-1, 'left')
        if m+1<=e: traverse(d+1, m+1, e, 'right')


traverse(1, 0, n-1, '')
print(ans)

Python: if __name__ == "__main__":
    num_nodes = int(input())
    P = list(map(lambda x: float(x), input().split()))
    Q = list(map(lambda x: float(x), input().split()))

    Depth = [[0] * (num_nodes + 1) for i in range(num_nodes + 1)]
    Exp = [[0.0] * (num_nodes + 1) for i in range(num_nodes + 1)]
    Cum_prob = [0.0] * (2 * num_nodes + 2)

    for i in range(2 * num_nodes + 1):
        Cum_prob[i + 1] = Cum_prob[i] + (P[i // 2] if i % 2 else Q[i // 2])

    for i in range(num_nodes + 1):
        Exp[i][i] = Q[i]
        Depth[i][i] = i

    for l in range(1, num_nodes + 1):
        for i in range(num_nodes + 1 - l):
            j = i + l
            d0 = Depth[i][j - 1]
            d1 = Depth[i + 1][j]
            d2 = -1
            cost = 1e30
            for k in range(d0, min(d1 + 1, j)):
                v = Exp[i][k] + Exp[k + 1][j]
                if v < cost:
                    d2 = k
                    cost = v
            Depth[i][j] = d2
            Exp[i][j] = cost + Cum_prob[2 * j + 1] - Cum_prob[2 * i]

    print(f"{Exp[0][num_nodes]:.5f}")

C++:     /*
　　　∫ ∫ ∫
　　　ノヽ
　　（＿　 ）
　（＿　　　 ）
（＿＿＿＿＿＿ ）
　ヽ(´･ω･)ﾉ　
　　 |　 /
　　 UU
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
using P = pair<ll, ll>;
const int MOD = (int)1e9 + 7;
const ll INF = 1LL << 60;
const int inf = 1<<30;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
#define REP(i, n) for (int i = 0; i < (n); i++)
#define FOR(i,s,n) for (int i = s; i < (n); i++)
#define ALL(obj) (obj).begin(), (obj).end() //コンテナじゃないと使えない!!
#define debug(x) cerr << #x << ": " << x << "\n";
#define mp make_pair
template <typename T>
ostream& operator<<(ostream& os, vector<T> &V){
    int N = V.size();
    REP(i,N){
        os << V[i];
        if (i!=N-1) os << " ";

    }
    os << "\n";
    return os;
}

ld solve(vector<ld>& P, int N){
    /*
        区間[s,t]をiで分割する
        　　　i
        　子    子
        ・・・　・・・
        にする(今回はダミーは関節点に来ないことに注意)
    
        すると、dp[s][t] = min(dp[s][i-1] + dp[i+1][t]) + (s~tのコストの和)で表せる  (s<i<t かつ　実際の(ダミーでない)ノード)
    */
   vector<vector<ld>> dp(N,vector<ld>(N,1<<30)); 
    for(int i=0;i<N;i++) dp[i][i] = P[i]; 
    
    vector<ld> cumsum(N+1,0);
    REP(i,N) {cumsum[i+1]=cumsum[i]+P[i];}  //累積和(s~tのコストの和をO(1)で使うために)
    for(int i=2 ;i<N;i+=2){ 
        for(int left=1;left < N-i;left+=2){ // ダミー,...,ダミーを単位としてやる
            int right = left + i; //区間右端(閉)
            for(int mid = left+1; mid<right; mid+=2){ //ダミーは関節点に来ない
                chmin(dp[left][right], dp[left][mid-1] + dp[mid+1][right]); //上記の分割
            }
            dp[left][right] += cumsum[right+1]-cumsum[left];
        }
    }
    ld res = dp[1][N-1]; //1-indexに注意
    return res;
}
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    int L = 2*(N+1);  
    vector<ld> P(L,0);//1-index   DVDVDVDVDVDVDVDVD (D:ダミー,V:実際の)
    REP(i,N) cin >> P[2*(i+1)];
    REP(i,N+1) cin >> P[2*i+1];

    ld ans=solve(P,L);
    cout << fixed<<setprecision(10)<<ans<<endl;
}