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