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])
}

C++: #include <bits/stdc++.h>

using namespace std;

typedef long long int ll;
typedef pair<ll, ll> pll;

#define FOR(i, n, m) for(ll (i)=(m);(i)<(n);++(i))
#define REP(i, n) FOR(i,n,0)
#define OF64 std::setprecision(40)

const ll MOD = 1000000007;
const ll INF = (ll) 1e15;

long double P[505], Q[505];
long double dp[505][505];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N;
    cin >> N;
    REP(i, N) {
        cin >> P[i];
    }
    REP(i, N + 1) {
        cin >> Q[i];
    }

    REP(i, N + 1) {
        REP(j, N + 1) {
            dp[i][j] = INF;
        }
    }

    REP(len, N) {
        REP(left, N) {
            if (left + len >= N)
                break;

            long double sum = Q[left + len + 1];
            REP(i, len + 1) {
                sum += P[left + i] + Q[left + i];
            }
            REP(i, len + 1) {
                //! 頂点iをroot
                long double p = sum;
                if (i == 0)
                    p += Q[left + i];
                else
                    p += dp[left][left + i - 1];

                if (i == len)
                    p += Q[left + i + 1];
                else
                    p += dp[left + i + 1][left + len];

                dp[left][left + len] = std::min(dp[left][left + len], p);
            }
        }
    }

    cout << OF64 << dp[0][N - 1] << endl;
    return 0;
}

C++: #include<bits/stdc++.h>

using namespace std;

typedef vector<double> vd;
const double INF=1e10;

class OBST
{
public:
    int n;
    vd p,q;
    vector<vd> e,w;

    OBST(int _n=1)
    {
        n=_n;
        p.resize(n+1);
        q.resize(n+1);
        e.resize(n+2,vd(n+1));
        w.resize(n+2,vd(n+1));
    }

    void get()
    {
        for(int i=1;i<=n;i++)
        {
            cin>>p[i];
        }
        for(int i=0;i<=n;i++)
        {
            cin>>q[i];
        }
    }

    double go()
    {
        for(int i=1;i<=n+1;i++){
            e[i][i-1]=w[i][i-1]=q[i-1];
        }

        for(int len=1;len<=n;len++)
        {
            for(int i=1;i<=n-len+1;i++)
            {

                int j=i+len-1;
                e[i][j]=INF;
                w[i][j]=w[i][j-1]+p[j]+q[j];
                for(int k=i;k<=j;k++)
                {
                    e[i][j]=min(e[i][j],e[i][k-1]+e[k+1][j]+w[i][j]);
                }
            }
        }
        return e[1][n];
    }
};

int main()
{
    int n;
    cin>>n;

    OBST obst(n);

    obst.get();

    cout<<obst.go()<<endl;

    return 0;
}

C++: #include <bits/stdc++.h>

#define NIL NULL
#define INF 1000000001

using namespace std;

int main(){
    // ---- iput ---- //
    int n;
    float temp;
    scanf("%d",&n);
    vector<float> p(n,0);
    vector<float> q(n+1,0);
    vector<vector<float> > cost(n+1,vector<float>(n+1,INF));
    for(int i = 0;i < n;i++){
        scanf("%f",&temp);
        p[i] = temp;
    } 
    for(int i = 0;i < n+1;i++){
        scanf("%f",&temp);
        q[i] = temp;
    } 

    for(int k = 0;k < n+1;k++){
        for(int i = 0;i < n-k+1;i++){
            int j = i + k;
            float w = q[i];
            if(j == i) cost[i][j] = w;
            else{
                for(int l =i+1;l <= j;l++) w += q[l]+p[l-1];
                for(int l =i;l < j;l++){
                    cost[i][j] = min(cost[i][j],cost[i][l]+cost[l+1][j] + w);
                }
            } 
        }
    }
    printf("%.5f\n",cost[0][n]);
    return 0;   
}

C++: #include <bits/stdc++.h>
using namespace std;

vector<double> p;
vector<double> q;
vector<double> psum;
vector<double> qsum;
double memo[502][502];

double dfs( int l, int r )
{
	if( memo[l][r] >= 0 ) return memo[l][r];
	if( l == r ) return memo[l][r] = 0;
	double res = DBL_MAX;
	double total = psum[r] - psum[l] + qsum[r] - qsum[l - 1];
	for( int x = l + 1; x <= r; x++ ) {
		double left = psum[x - 1] - psum[l] + qsum[x - 1] - qsum[l - 1];
		double right = total - left - p[x - 2];
		double w = (dfs( l, x - 1 ) + 1) * left / total + (dfs( x, r ) + 1) * right / total;
		res = min( res, w );
	}
	memo[l][r] = res;
	return res;
}

int main()
{
	int n;
	cin >> n;
	p = vector<double>( n );
	for( int i = 0; i < n; i++ ) cin >> p[i];
	q = vector<double>( n + 1 );
	for( int i = 0; i < n + 1; i++ ) cin >> q[i];

	memset( memo, -1, sizeof( memo ) );
	psum = vector<double>( n + 2 );
	for( int i = 2; i < n + 2; i++ ) psum[i] = psum[i - 1] + p[i - 2];
	qsum = vector<double>( n + 2 );
	for( int i = 1; i < n + 2; i++ ) qsum[i] = qsum[i - 1] + q[i - 1];
	double ans = dfs( 1, n + 1 ) + 1;

	cout << fixed << setprecision(8) << ans << endl;
}

C++: #include <iostream>
#include <vector>
#include <float.h>

int main() {
	int n;
	std::cin >> n;
	std::vector<double> p(n, 0);
	std::vector<double> q(n + 1, 0);
	std::vector<std::vector<double>> CostMat(n, std::vector<double>(n, 0));

	for (int i = 0; i < n; i++) {
		std::cin >> p[i];
	}
	for (int i = 0; i < n + 1; i++) {
		std::cin >> q[i];
	}

	// 対角成分
	for (int i = 0; i < n; i++) {
		CostMat[i][i] = p[i] + 2.0 * q[i] + 2.0 * q[i + 1];
	}

	// 動的計画法により最小コストを求める
	for (int i = 1; i < n; i++) {
		for (int j = 0; j < n - i; j++) {
			double min = DBL_MAX;
			for (int l = 0; l <= i; l++) {
				double tmp = 0;
				if (l != i) {
					tmp += CostMat[j + l + 1][i + j];
				}
				if (l != 0) {
					tmp += CostMat[j][j + l - 1];
				}
				if (l == 0) {
					tmp += q[j];
				}
				if (l == i) {
					tmp += q[j + i + 1];
				}
				if (tmp < min) {
					min = tmp;
				}
			}
			//std::cout << min << std::endl;
			CostMat[j][i + j] = min;
			for (int k = j; k <= j + i; k++) {
				CostMat[j][i + j] += p[k] + q[k];
			}
			CostMat[j][i + j] += q[j + i + 1];
		}
	}

	std::cout << CostMat[0][n - 1] << std::endl;
}

C++: #include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<list>
#include<string>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;

const int NIL = -1;
const int MAX = 20001;
int root[510][510];
double w[510][510];
double e[510][510];

int main(void)
{
	int n;
	double P, Q, t;
	vector<double>p, q;
	cin >> n;
	p.push_back(0);
	for (int i = 0; i < n; i++) {
		cin >> P;
		p.push_back(P);
	}
	for (int i = 0; i < n + 1; i++) {
		cin >> Q;
		q.push_back(Q);
	}
	for (int i = 1; i <= n + 1; i++) {
		e[i][i - 1] = q[i - 1];
		w[i][i - 1] = q[i - 1];
	}
	for (int l = 1; l <= n; l++) {
		for (int i = 1; i <= n - l + 1; i++) {
			int j = i + l - 1;
			e[i][j] = MAX;
			w[i][j] = w[i][j - 1] + p[j] + q[j];
			for (int r = i; r <= j; r++) {
				t = e[i][r - 1] + e[r + 1][j] + w[i][j];
				if (t < e[i][j]) {
					e[i][j] = t;
					root[i][j] = r;
				}
			}
		}
	}
	printf("%.8lf\n", e[1][n]);
	return 0;
}