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