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>
#include <cmath>

using namespace std;
typedef long long ll;
//typedef unsigned long long ll;

//#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep(i, n) for (ll i = 0; i < (n); ++i)
//#define sz(x) ll(x.size())
//typedef pair<ll, int> P;
//typedef pair<ll, ll> P;
const double INF = 1e10;
//const ll INF = LONG_LONG_MAX / 10;
//const ll INF = 1e15;
const ll MINF = LONG_LONG_MIN;
//const int INF = INT_MAX / 10;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)

bool contain(set<char> &s, int a) { return s.find(a) != s.end(); }

//ifstream myfile("C:\\Users\\riku\\Downloads\\0_00.txt");
//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;
// std::cout << std::bitset<8>(9);

typedef pair<double, double> P;

void print_line(vector<int> &line) {
    if (line.size() == 0ll) {
        cout << endl;
        return;
    }
    for (ll i = 0; i < line.size(); i++) {
        cout << line[i];
        if (i == line.size() - 1) cout << endl;
        else cout << ' ';
    }
}


typedef priority_queue<long long, vector<long long>, greater<long long>> PQ_ASK;
const int mod = 1000000007;

int main() {
    int n;


    cin >> n;
    vector<P> ks(n + 1, P(0, 0));
    vector<vector<double>> p_sum(n + 1, vector<double>(n + 1, 0));
    vector<vector<double>> q_sum(n + 1, vector<double>(n + 1, 0));
    vector<vector<double>> dp(n + 1, vector<double>(n + 1, 0));;

    for (int i = 0; i < n; ++i) cin >> ks[i].first;
    for (int i = 0; i < n + 1; ++i) cin >> ks[i].second;
    for (int i = 0; i < n + 1; ++i) dp[i][i] = ks[i].second;

    for (int i = 0; i < n; ++i) {
        p_sum[i][i] = ks[i].first;
        for (int j = i + 1; j < n; ++j) {
            p_sum[i][j] = p_sum[i][j - 1] + ks[j].first;
        }
    }

    for (int i = 0; i < n + 1; ++i) {
        q_sum[i][i] = ks[i].second;
        for (int j = i + 1; j < n + 1; ++j) {
            q_sum[i][j] = q_sum[i][j - 1] + ks[j].second;
        }
    }

    for (int i = 1; i < n + 1; ++i) {
        for (int j = 0; j < (n + 1) - i; ++j) {
            dp[j][j + i] = INF;
            for (int k = 0; k < i; ++k) {
                double t = dp[j][j + k] + dp[j + k + 1][j + i] + p_sum[j][j + i - 1] + q_sum[j][j + i];
                dp[j][j + i] = min(dp[j][j + i], t);
            }
        }
    }

    printf("%.20f\n", dp[0][n]);

}

C++: #include<bits/stdc++.h>
#define ll long long
#define rep(i, n) for(int i=0;i<(n);++i)
#define per(i, n) for(int i=(n)-1;i>=0;--i)
#define repa(i, n) for(int i=1;i<(n);++i)
#define foreach(i, n) for(auto &i:(n))
#define pii pair<int, int>
#define pll pair<long long, long long>
#define all(x) (x).begin(), (x).end()
#define bit(x) (1ll << (x))
const ll MOD = (ll)1e9+7;
const int INF = (ll)1e9+7;
const ll INFLL = (ll)1e18;
using namespace std;
template<class t>
using vvector = vector<vector<t>>;
template<class t>
using vvvector = vector<vector<vector<t>>>;
template<class t>
using priority_queuer = priority_queue<t, vector<t>, greater<t>>;
template<class t, class u> bool chmax(t &a, u b){if(a<b){a=b;return true;}return false;}
template<class t, class u> bool chmin(t &a, u b){if(a>b){a=b;return true;}return false;}

ll modpow(ll x, ll b){
	ll res = 1;
	while(b){
		if(b&1)res = res * x % MOD;
		x = x * x % MOD;
		b>>=1;
	}
	return res;
}

ll modinv(ll x){
	return modpow(x, MOD-2);
}

int n;
vector<double> p;
vector<double> sump;
vector<double> q;
vector<double> sumq;
vvector<double> dp;

double func(int l, int r){
	if(r<l)return 0;
	if(l==r){
		return p[l] + 2 * q[l-1] + 2 * q[l];
	}
	if(dp[l][r] >= 0)return dp[l][r];
	double res = INFLL;
	chmin(res, q[l-1]*2+p[l]+func(l+1, r)+sump[r]-sump[l]+sumq[r]-sumq[l-1]);
	chmin(res, q[r]*2+p[r]+func(l, r-1)+sump[r-1]-sump[l-1]+sumq[r-1]-sumq[l-2]);
	for(int mid=l+1;mid<r;++mid){
		double midsum = p[mid];
		double leftsum = func(l, mid-1) + sump[mid-1] - sump[l-1] + sumq[mid-1] - sumq[l-2];
		double rightsum = func(mid+1, r) + sump[r] - sump[mid] + sumq[r] - sumq[mid-1];
		chmin(res, midsum+leftsum+rightsum);
	}
	return dp[l][r] = res;
}

int main(){
	cin >> n;
	p.resize(n+2);
	q.resize(n+3);
	sump.resize(n+3, 0);
	sumq.resize(n+4, 0);
	for(int i=2;i<n+2;++i){
		cin >> p[i];
		sump[i] = sump[i-1] + p[i];
	}
	for(int i=1;i<n+2;++i){
		cin >> q[i];
		sumq[i] = sumq[i-1] + q[i];
	}
	dp.resize(n+2, vector<double>(n+2, -1));
	printf("%.8lf\n", func(2, n+1));
	return 0;
}

C++: #include <bits/stdc++.h>

int main()
{
	int n;
	scanf("%d", &n);

	using vd = std::vector<double>;
	using vvd = std::vector<vd>;
	vd percentage(2 * n + 2);
	for (int i{2}; i < 2 * n + 2; i += 2)
		scanf("%lf", &percentage[i]);
	for (int i{1}; i < 2 * n + 2; i += 2)
		scanf("%lf", &percentage[i]);

	vvd dp(n + 1, vd(n + 1, 9));
	for (int i{}; i <= n; i++)
		dp[i][i] = 0;

	for (int i{1}; i < 2 * n + 2; i++)
		percentage[i] += percentage[i - 1];

	for (int width{1}; width <= n; width++)
		for (int left{}; left + width <= n; left++)
		{
			int right{left + width};
			for (int root{right}; root > left; root--)
				dp[left][right] = std::min(dp[left][right],
				dp[left][root - 1] + percentage[2 * root - 1] - percentage[2 * left]
				+ dp[root][right] + percentage[2 * right + 1] - percentage[2 * root]
				);
		}

	std::cout << std::fixed << std::setprecision(6) << dp[0][n] + 1 << std::endl;

	return 0;
}