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

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