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<bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i) 
#define PI acos(-1)

using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using LP = pair<ll, ll>;

template<class T> inline bool chmax(T& a, T b) {if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) {if (a > b) { a = b; return true; } return false; }

#define INF 1001001

double dpRec(int l, int r, vector<vector<double>>& dp, vector<vector<int>>& key, vector<double> sump, vector<double> sumq) {
    if (dp[l][r] != INF) return dp[l][r];
    if (l > r) {
        dp[l][r] = sumq[r + 1] - sumq[l - 1];
        return dp[l][r];
    }

    double s = sump[r] - sump[l - 1] + sumq[r + 1] - sumq[l - 1];

    if (chmin(dp[l][r], dpRec(l, l - 1, dp, key, sump, sumq) + dpRec(l + 1, r, dp, key, sump, sumq) + s)) {
        key[l][r] = l;
    }
    if (l == r) return dp[l][r];
    
    if (chmin(dp[l][r], dpRec(l, r - 1, dp, key, sump, sumq) + dpRec(r + 1, r, dp, key, sump, sumq) + s)) {
        key[l][r] = r;
    }

    for (int i = key[l][r - 1]; i <= key[l + 1][r]; ++i) {
        if (chmin(dp[l][r], dpRec(l, i - 1, dp, key, sump, sumq) + dpRec(i + 1, r, dp, key, sump, sumq) + s)) {
            key[l][r] = i;
        }
    }
    return dp[l][r];
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n;
    cin>>n;
    vector<double> ps(n), sump(n + 1), qs(n + 1), sumq(n + 2);
    rep(i, n) {
        cin>>ps[i];
        sump[i + 1] = sump[i] + ps[i];
    }
    rep(i, n + 1) {
        cin>>qs[i];
        sumq[i + 1] = sumq[i] + qs[i];
    }

    vector<vector<double>> dp(n + 2, vector<double>(n + 2, INF));
    vector<vector<int>> key(n + 2, vector<int>(n + 2, INF));
    double ans = dpRec(1, n, dp, key, sump, sumq);
    printf("%.10f\n", ans);
}

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;

}