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<iomanip>
#include<limits>
#include<thread>
#include<utility>
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<numeric>
#include<cassert>
#include<random>
#include<chrono>
#include<unordered_set>
#include<unordered_map>
#include<fstream>
#include<list>
#include<functional>
#include<bitset>
#include<complex>
#include<tuple>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef long double D;
typedef complex<D> P;
#define F first
#define S second
const ll E=1e18+7;
const ll MOD=1000000007;


template<typename T,typename U>istream & operator >> (istream &i,pair<T,U> &A){i>>A.F>>A.S; return i;}
template<typename T>istream & operator >> (istream &i,vector<T> &A){for(auto &I:A){i>>I;} return i;}
template<typename T,typename U>ostream & operator << (ostream &o,pair<T,U> &A){o<<A.F<<" "<<A.S; return o;}
template<typename T>ostream & operator << (ostream &o,vector<T> &A){ll i=A.size(); for(auto &I:A){o<<I<<(--i?" ":"");} return o;}
template<typename T>vector<T> & cset(vector<T> &A,T e=T()){for(auto &I:A){I=e;} return A;}



int main(){
    ll n;
    cin>>n;
    vector<D> ps(n),qs(n+1);
    cin>>ps>>qs;
    ll N=2*n+1;
    vector<D> A(N);
    for(int i=0;i<n;i++){A[i*2+1]=ps[i];}
    for(int i=0;i<=n;i++){A[i*2]=qs[i];}
    for(int i=1;i<N;i++){A[i]+=A[i-1];}
    auto sum=[&](ll l,ll r){return A[r]-(l==0?0:A[l-1]);};
    vector<vector<D>> dp(N,vector<D>(N,E));
    vector<vector<ll>> K(N,vector<ll>(N,0));
    for(int i=0;i<N;i+=2){dp[i][i]=sum(i,i); K[i][i]=i;}
    for(int i=2;i<N;i+=2){
        for(int j=0;j+i<N;j+=2){
            ll l=K[j][i+j-2],r=K[j+2][i+j];
            for(ll k=l;k<=r;k++){
                if(k&1 && j<k && k<i+j && dp[j][i+j]>dp[j][k-1]+dp[k+1][i+j]){
                    dp[j][i+j]=dp[j][k-1]+dp[k+1][i+j];
                    K[j][i+j]=k;
                }
            }
            dp[j][i+j]+=sum(j,i+j);
        }
    }
    cout<<fixed<<setprecision(12)<<dp[0].back()<<endl;
    
    return 0;
}

C++: #include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <functional>
#include <map>
#include <climits>
#include <stack>
#include <string>
#include <random>
#include<set>
#include <iomanip>
#include <climits>

class Probability {
	std::vector<double> key_probabilities, dummy_probabilities;
public:
	Probability(const std::vector<double> &keys, const std::vector<double> &dummies) {
		key_probabilities.push_back(0); dummy_probabilities.push_back(0);
		for (const auto k : keys) {
			key_probabilities.push_back(key_probabilities.back() + k);
		}
		for (const auto d : dummies) {
			dummy_probabilities.push_back(dummy_probabilities.back() + d);
		}
	}
	double sum_key(const int from, const int until) const {
		return key_probabilities[until] - key_probabilities[from];
	}
	double sum_dummy(const int from, const int until) const {
		return dummy_probabilities[until] - dummy_probabilities[from];
	}
	double key(const int position) const {
		return key_probabilities[position + 1] - key_probabilities[position];
	}
	double dummy(const int position) const {
		return dummy_probabilities[position + 1] - dummy_probabilities[position];
	}
};
constexpr double NA = -1;
double sub_sequence(const int from, const int until, std::vector<std::vector<double>> &memo, const Probability &prob) {
	if (from == until) return prob.dummy(from);
	if (memo[from][until - from - 1] != NA) return memo[from][until - from - 1];
	double min = 500 * 500;
	for (auto mid = from; mid < until; ++mid) {
		auto seq = sub_sequence(from, mid, memo, prob) + sub_sequence(mid + 1, until, memo, prob) + prob.sum_key(from, until) + prob.sum_dummy(from, until + 1);
		if (min > seq) min = seq;
	}
	return memo[from][until - from - 1] = min;
}
int main() {
	int n; std::cin >> n;
	std::vector<double> key(n); for (auto &k : key) std::cin >> k;
	std::vector<double> dummy(n + 1); for (auto &d : dummy) std::cin >> d;
	Probability sum(key, dummy);
	std::vector<std::vector<double>> memo;
	for (auto i = 0; i < n; ++i) {
		memo.push_back(std::vector<double>(n - i, NA));
	}
	std::cout << sub_sequence(0, n, memo, sum) << std::endl;

}

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

using namespace std; 

int main(void) {
	int n;
	cin >> n;
	vector<double> p(n+1);
	p[0] = 1;
	for (int i = 0; i < n; ++i) {
		cin >> p[i+1];
	}
	vector<double> q(n+1);
	vector< vector<double> > sum(n+1,vector<double>(n+1));
	vector< vector<double> > dp(n+1,vector<double>(n+1,(1 << 28)));
	for (int i = 0; i < n+1; ++i) {
		cin >> q[i];
		if (i > 0) {
			dp[i][i] = p[i]+(2*(q[i-1]+q[i]));
			sum[i][i] = dp[i][i] - (q[i-1]+q[i]); 
		}
	}
	for (int i = 1; i < n+1; ++i) {
		for (int j = i+1; j < n+1; ++j) {
			sum[i][j] = sum[i][j-1] + sum[j][j] - q[j-1];
		}
	}
	double rc,left,right;
	for (int k = 2; k < n+1; ++k) {
		for (int i = 1; i < n-k+2; ++i) {
			for (int j = 0; j < k; ++j) {
				rc = dp[i+j][i+j];
				left = right = 0;
				if (j != 0) {
					rc -= 2*q[i+j-1];
					left += dp[i][i+j-1] + sum[i][i+j-1];
				}
				if (j != k-1) {
					rc -= 2*q[i+j];
					right += dp[i+j+1][i+k-1] + sum[i+j+1][i+k-1];
				}
				dp[i][i+k-1] = min(rc+left+right,dp[i][i+k-1]);
			}
		}
	}
	cout << setprecision(20) << fixed << dp[1][n] << endl;

	return 0;
}