Go: package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"strconv"
)

var scanner = bufio.NewScanner(os.Stdin)

func nextString() string {
	scanner.Scan()
	return scanner.Text()
}

func nextInt() int {
	n, err := strconv.Atoi(nextString())
	if err != nil {
		fmt.Printf("strconv.Atoi failed: %v\n", err)
	}
	return n
}

func nextFloat64() (float64, error) {
	return strconv.ParseFloat(nextString(), 64)
}

var infty = math.MaxFloat64

func optimalBst(p []float64, q []float64, n int) ([][]float64, [][]int) {
	e := make([][]float64, n+2)
	for i := 0; i <= n+1; i++ {
		e[i] = make([]float64, n+1)
	}
	w := make([][]float64, n+2)
	for i := 0; i <= n+1; i++ {
		w[i] = make([]float64, n+1)
	}
	root := make([][]int, n+1)
	for i := 0; i <= n; i++ {
		root[i] = make([]int, n+1)
	}

	for i := 1; i <= n+1; i++ {
		e[i][i-1] = q[i-1]
		w[i][i-1] = q[i-1]
	}
	for l := 1; l <= n; l++ {
		for i := 1; i <= n-l+1; i++ {
			j := i + l - 1
			e[i][j] = infty
			w[i][j] = w[i][j-1] + p[j] + q[j]
			for 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
				}
			}
		}
	}

	return e, root
}

func main() {
	scanner.Split(bufio.ScanWords)

	n := nextInt()
	p := make([]float64, n+1)
	q := make([]float64, n+1)
	for i := 1; i <= n; i++ {
		p[i], _ = nextFloat64()
	}
	for i := 0; i <= n; i++ {
		q[i], _ = nextFloat64()
	}

	// fmt.Println(p)
	// fmt.Println(q)

	e, _ := optimalBst(p, q, n)

	// fmt.Println(root)
	fmt.Println(e[1][n])
}

C++: #include<iostream>
#include<cfloat>
#include<algorithm>

using namespace std;

int main() {
	int n;
	cin >> n;
	float* p = new float[n];
	float* q = new float[n + 1];
	float sum, mini;
	for (int i = 0;i < n;i++) {
		cin >> p[i];
	}
	for (int i = 0;i <= n;i++) {
		cin >> q[i];
	}
	float** cost = new float* [n];
	float** coefficient = new float* [n];
	for (int i = 0;i < n;i++) {
		cost[i] = new float[n - i];
		coefficient[i] = new float[n - i];
	}
	for (int i = 0;i < n ;i++) {
		for (int j = 0;j < n - i;j++) {
			sum = 0;
			for (int k = i;k <= i + j;k++) {
				sum += p[k] + q[k];
			}
			sum += q[i + j + 1];
			coefficient[i][j] = sum;
		}
		cost[i][0] = p[i]+2*q[i]+2*q[i+1];
	}
	for (int j = 1;j <n;j++) {
		for (int i = 0;i < n - j;i++) {
			mini = p[i] + cost[i + 1][j - 1] + coefficient[i + 1][j - 1]+2*q[i];
			for (int k = 1;k < j;k++) {
				mini = min(mini, p[i + k] + cost[i][k - 1] + coefficient[i][k - 1] + cost[i + k + 1][j - k - 1] + coefficient[i + k + 1][j - k - 1]);
			}
			cost[i][j] = min(mini, p[i + j] + cost[i][j - 1] + coefficient[i][j - 1] + 2 * q[i + j + 1]);
		}
	}
	cout << cost[0][n-1] << endl;
}

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;
}