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>

double min(double x, double y)
{
	return x>y ? y : x;
}

int main()
{
	std::string strn; getline(std::cin, strn);
	int n = std::stoi(strn);
	
	double *p = new double[n];
	double *q = new double[n+1];
	
	for (int i=0; i<n; i++) std::cin >> p[i];  // p[0], p[1], ... , p[n-1]
	for (int i=0; i<=n; i++) std::cin >> q[i]; // q[0], q[1], ... , q[n-1], q[n]
	
	double *cost_sum = new double[n+1];
	cost_sum[0] = q[0];
	for (int i=1; i<n+1; i++) cost_sum[i] = cost_sum[i-1] + p[i-1] + q[i]; 
	
	double** DP = new double*[n+1];
	for (int i=0; i<n+1; i++) DP[i] = new double[n];
	
	for (int j=0; j<n; j++) DP[j+1][j] = 0.0;
	
	for (int d=0; d<n; d++) {
		for (int i=0; i<n-d; i++) {
			if (d==0) DP[i][i] = q[i] + q[i+1];
			else {
				DP[i][i+d] = DBL_MAX;
				for (int j=0; j<=d; j++) {
					double left_cost_sum  = cost_sum[i+j] - cost_sum[i] + q[i];
					double right_cost_sum = cost_sum[i+d+1] - cost_sum[i+j+1] + q[i+j+1];
					DP[i][i+d] = min(DP[i][i+d], DP[i][i+j-1] + left_cost_sum + DP[i+j+1][i+d] + right_cost_sum);
				}
			}
			// std::cout << "DP[" << i << "][" << i+d << "] = " << DP[i][i+d] << std::endl;
		}
	}
	
	std::cout << std::fixed << DP[0][n-1] + 1 << std::endl;
	
	for (int i=0; i<n; i++) delete[] DP[i];
	delete[] DP;
	delete[] cost_sum;
	delete[] p;
	delete[] q;
	
	return 0;
}

C++: #include <iomanip>
#include <iostream>
#include <vector>

using namespace std;
using ld = long double;

template <class T>
T Vec(T v) { return v; }

template <class T, class... Ts>
auto Vec(size_t l, Ts... ts) {
    return vector<decltype(Vec<T>(ts...))>(l, Vec<T>(ts...));
}

int N;
vector<ld> psum;

ld rec(int l, int r) {
    if (l == r) return psum[r] - psum[l - 1];
    static auto dp = Vec<ld>((N + 1) * 2, (N + 1) * 2, -1.L);
    if (dp[l][r] >= 0) return dp[l][r];

    dp[l][r] = 1e30;
    for (int p = l + 1; p < r; p += 2) {
        dp[l][r] = min(dp[l][r], rec(l, p - 1) + rec(p + 1, r));
    }
    return dp[l][r] += psum[r] - psum[l - 1];
}

int main() {
    cin >> N;
    psum.resize((N + 1) * 2);
    psum[0] = 0;
    for (int i = 1; i <= N; ++i) cin >> psum[i * 2];
    for (int i = 0; i <= N; ++i) cin >> psum[i * 2 + 1];
    for (int i = 1; i < (N + 1) * 2; ++i) psum[i] += psum[i - 1];

    cout << fixed << setprecision(10) << rec(1, N * 2 + 1) << endl;
    return 0;
}

C++: #include<bits/stdc++.h>
using namespace std;
using UL = unsigned int;
using ULL = unsigned long long;
using LL = long long;
#define rep(i,n) for(int i=0; i<(n); i++)

int N;
int P[600];
int Q[600];
int S[600][2];
int dp[600][600];

int input10000(){
 double x; scanf("%lf",&x);
 return floor(x*10000+0.5);
}

int main() {
 scanf("%d",&N);
 rep(i,N) P[i]=input10000(); P[N]=-1;
 rep(i,N+1) Q[i]=input10000(); Q[N+1]=-1;

 S[0][0]=S[0][1]=0;
 for(int i=1; i<=N; i++){
  S[i][0]=S[i-1][1]+Q[i-1];
  S[i][1]=S[i][0]+P[i-1];
 }
 S[N+1][0]=S[N][1]+Q[N];

 rep(i,N+2) rep(j,N+2) dp[i][j]=1000000000;
 rep(i,N+1) dp[i][i+1]=0;

 rep(d,N+2) rep(p,N+2-d){
  if(d<2) continue;
  for(int s=p+1; s<p+d; s++){
   int tmp=0;
   tmp += dp[p][s] + S[s][0]-S[p][1];
   tmp += dp[s][p+d] + S[p+d][0]-S[s][1];
   dp[p][p+d] = min(dp[p][p+d],tmp);
  }
 }

 double ans=dp[0][N+1];
 ans = (ans/10000.0)+1.0;
 printf("%.10f\n",ans);
 
 return 0;
}

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<iomanip>
#include<vector>
using namespace std;

double OptimalBSTree(const vector<double>& p, const vector<double>& q, const int n){
    vector<vector<double>> psum(n, vector<double>(n));
	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<double>> qsum(n + 1, vector<double>(n + 1));
	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];
			}
		}
	}

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

int main(){
	int n;
	cin >> n;
    // n 個の各キーに対して探索が起きる確率 p
    // n+1 個の各ダミーキーで探索が終わる確率 q
	vector<double> p(n), q(n + 1);
	for(int i = 0; i < n; i++){
		cin >> p[i];
	}
	for(int i = 0; i < n + 1; i++){
        cin >> q[i];
	}

    cout << fixed << setprecision(4) << OptimalBSTree(p, q, n) << endl;

	return 0;
}