Go: package main

import (
	"bufio"
	"fmt"
	"log"
	"math"
	"os"
	"strconv"
	// "github.com/pkg/profile"
)

func mkTbl(n int, ds []float64) [][]float64 {
	tbl := make([][]float64, n+1)
	for i := range tbl {
		tbl[i] = make([]float64, n+1)
	}
	for i := 0; i <= n; i++ {
		tbl[i][i] = ds[i]
	}
	return tbl
}

func mkWeights(n int, ps, ds []float64) [][]float64 {
	tbl := mkTbl(n, ds)
	for i := 0; i < n; i++ {
		w := ds[i]
		for j := i + 1; j <= n; j++ {
			w += ps[j] + ds[j]
			tbl[i][j] = w
		}
	}
	return tbl
}

func minCost(i, j int, tbl [][]float64) float64 {
	m := math.MaxFloat64
	for k := i + 1; k <= j; k++ {
		m = math.Min(m, tbl[i][k-1]+tbl[k][j])
	}
	return m
}

func solve(n int, ps, ds []float64) float64 {
	costs := mkTbl(n, ds)
	weights := mkWeights(n, ps, ds)
	for l := 1; l <= n; l++ {
		for i := 0; i <= n-l; i++ {
			j := i + l
			costs[i][j] = weights[i][j] + minCost(i, j, costs)
		}
	}
	return costs[0][n]
}

func main() {
	// defer profile.Start(profile.ProfilePath(".")).Stop()

	w := bufio.NewWriter(os.Stdout)
	s := bufio.NewScanner(os.Stdin)
	s.Split(bufio.ScanWords)

	s.Scan()
	n, _ := strconv.Atoi(s.Text())
	ps := make([]float64, n+1)
	ds := make([]float64, n+1)

	for i := 1; i <= n; i++ {
		s.Scan()
		ps[i], _ = strconv.ParseFloat(s.Text(), 64)
	}

	for i := 0; i < n+1; i++ {
		s.Scan()
		ds[i], _ = strconv.ParseFloat(s.Text(), 64)
	}

	if s.Err() != nil {
		log.Fatal("scan error")
	}

	fmt.Fprintf(w, "%.4f\n", solve(n, ps, ds))
	_ = w.Flush()
}

C++: #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
//const ll mod = 1000000007;5
double dp[505][505];
int n;
double p[505];
double q[505];
double psum[505];
double qsum[505];

double search(int l, int r) {
    if(dp[l][r] != 0) return dp[l][r];
    if(l == r) {
        return dp[l][r] = 0;
    }
    dp[l][r] = 1e9;
    double total = qsum[r] - qsum[l-1] + psum[r] - psum[l];
    for(int x = l + 1; x <= r; x++) {
        double left = qsum[x-1] - qsum[l-1] + psum[x-1] - psum[l];
        double right = total - left - p[x];
        double now = (search(l, x - 1) + 1) * (left / total) + (search(x, r) + 1) * (right / total);
        dp[l][r] = min(dp[l][r], now);
    }
    return dp[l][r];
}

int main() {
    cout.precision(10);
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n;
    for(int i = 2; i <= n + 1; i++) cin >> p[i];
    for(int i = 1; i <= n + 1; i++) cin >> q[i];
    for(int i = 1; i <= n + 1; i++) psum[i] = psum[i-1] + p[i];
    for(int i = i; i <= n + 1; i++) qsum[i] = qsum[i-1] + q[i];
    cout << 1.0 + search(1, n+1) << endl;
    return 0;
}

C++: #include <iostream>
#include <stdio.h>
#define MAX 501
using namespace std;

int main(int argc, char *argv[])
{
    int n;
    scanf("%d", &n);
    double p[MAX], q[MAX];
    p[0] = -1;
    for (int i = 1; i <= n; i++)
    {
        scanf("%lf", &p[i]);
    }
    for (int i = 0; i < n + 1; i++)
    {
        scanf("%lf", &q[i]);
    }

//    const int n = 5;
//      double p[n + 1] = {-1,0.15,0.1,0.05,0.1,0.2};
//     double q[n + 1] = {0.05,0.1,0.05,0.05,0.05,0.1};

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

    int j = 0;
    for (int l = 1; l <= n; l++)
    {
        for (int i = 1; i <= n - l + 1; i++)
        {
            j = i + l - 1;
            e[i][j] = (1 << 21);
            w[i][j] = w[i][j - 1] + p[j] + q[j];
            for (int r = i; r <= j; r++)
            {
                double t = e[i][r - 1] + e[r + 1][j] + w[i][j];
                if (t < e[i][j])
                {
                    e[i][j] = t;
                }
            }
        }
    }
    printf("%lf", e[1][n]);

    return 0;
}

C++: #include <stdio.h>
#include <iostream>
#include <algorithm>

using namespace std;
#define N 501

int main(){
    int n;
    double p[N],q[N];
    double pSum[N][N],qSum[N][N];
    double d[N][N];
    double t;
    
    cin >> n;
    
    for(int i = 0;i < n;++i){
        cin >> p[i];
    }
    
    for(int i = 0;i < n + 1;++i){
        cin >> q[i];
        d[i][i] = q[i];
    }
    
     // p
    for(int i = 0;i < n;++i){
        pSum[i][i] = p[i];
        for(int j = i + 1;j < n;++j){
            pSum[i][j] = pSum[i][j - 1] + p[j];
        }
    }
    
    // q
    for(int i = 0;i < n + 1;++i){
        qSum[i][i] = q[i];
        for(int j = i + 1;j < n + 1;++j){
            qSum[i][j] = qSum[i][j - 1] + q[j];
        }
    }
    
    for(int i = 1;i < n + 1;++i){
        for(int j = 0;j < (n + 1) - i;++j){
            d[j][j + i] = __DBL_MAX__;
            for(int k = 0;k < i;++k){
                t = d[j][j + k] + d[j + k + 1][j + i] + pSum[j][j + i - 1] + qSum[j][j + i];
                d[j][j + i] = min(d[j][j + i], t);
            }
        }
    }
    
    printf("%.8lf\n",d[0][n]);
    
    return 0;
}

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

#define INF 1e9
vector<double> p, q;

double memo[504][504];
double psum[504];
double qsum[504];

// [l,r)の木を構成した時に含まれる p,qの和
double sum(int l, int r) {
  assert(r > l);
  return psum[r] - psum[l] + qsum[r] - qsum[l - 1];
}

// [l, r)の区間について木にした時のコスト期待値
double dfs(int l, int r) {
  // 1個の時
  if (l + 1 == r) {
    // 今の深さ × p, 次の深さ x q (ダミーノード分)
    return p[l] + 2 * (q[l - 1] + q[l]);
  }
  if (memo[l][r] != -1) return memo[l][r];

  double ret = INF;
  // m を根にする分け方
  for (int m = l; m < r; m++) {
    double root, left, right;
    // 根の分
    root  = p[m];
    // 左部分木
    if (l == m) left  = 2 * q[l - 1];          // 端なのでダミー
    else        left  = dfs(l, m) + sum(l, m); // [l,m)の木の解 + l~mまでの和([l,m)の木の深さを1つ増やす)

    // 右部分木
    if (r - 1 == m) right = 2 * q[r - 1];      // 端なのでダミー
    else            right = dfs(m + 1, r) + sum(m + 1, r);
    
    ret = min(ret, root + left + right);
  }
  return memo[l][r] = ret;
}

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

  for (int i = 0; i < 502; i++) for (int j = 0; j < 502; j++) {
    memo[i][j] = -1;
  }

  cout << fixed << setprecision(10) << dfs(1, n + 1) << endl;

  return 0;
}

C++: #include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

float OptimalBSTree(vector<float> p, vector<float> q){
	int n = p.size();

	vector< vector<float> > psum(n, vector<float>(n, 0));
	for (int i = 0; i < n; i++){
		for (int j = 0; j < n - i; j++){
			if (i == 0){
				psum[j][j] = p[j];
			}
			else{
				psum[j][j + i] = psum[j][j + i - 1] + p[j + i];
			}
		}
	}
	vector< vector<float> > qsum(n + 1, vector<float>(n + 1, 0));
	for (int i = 0; i < n + 1; i++){
		for (int j = 0; j < n + 1 - i; j++){
			if (i == 0){
				qsum[j][j] = q[j];
			}
			else{
				qsum[j][j + i] = qsum[j][j + i - 1] + q[j + i];
			}
		}
	}

	float et;
	vector< vector<float> > table(n + 1, vector<float>(n + 1, 0));
	for (int i = 0; i < n + 1; i++){
		for (int j = 0; j < n + 1 - i; j++){
			if (i == 0){
				table[j][j] = q[j];
			}
			else{
				float min;
				for (int k = 0; k < i; k++){
					et = table[j][j + k] + table[j + k + 1][j + i] + psum[j][i + j - 1] + qsum[j][i + j];
					if (k == 0 || et < min) min = et;
				}
				table[j][j + i] = min;
			}
		}
	}
	return table[0][n];
}

int main(){
	int n;
	scanf("%d", &n);
	vector<float> p(n), q(n + 1);
	for (int i = 0; i < n; i++){
		scanf("%f", &p[i]);
	}
	for (int i = 0; i < n + 1; i++){
		scanf("%f", &q[i]);
	}
	printf("%f\n", OptimalBSTree(p, q));

	return 0;
}