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 <cstdio>
#include <cfloat>
#include <vector>
using namespace std;

#define v vector

struct OBST {
	typedef vector<double> vd;
	vd p, q;
	v<vd> e, w;

	void read(int n) {
		p.resize(n + 1);
		q.resize(n + 1);
		for (int i = 1; i <= n; i++)
			scanf("%lf", &p[i]);
		for (int i = 0; i <= n; i++)
			scanf("%lf", &q[i]);
	}

	double cost(int n) {
		e = v<vd>(n + 2, vd(n + 1));
		w = v<vd>(n + 2, vd(n + 1));
		for (int i = 0; i <= n; i++) {
			e[i + 1][i] = q[i];
			w[i + 1][i] = q[i];
		}
		for (int l = 1; l <= n; l++)
			for (int i = 1; i <= n - l + 1; i++) {
				int j = i + l - 1;
				e[i][j] = DBL_MAX;
				w[i][j] = w[i][j - 1] + p[j] + q[j];
				for (int r = i; r <= j; r++)
					e[i][j] = min(e[i][j], e[i][r - 1] + e[r + 1][j] + w[i][j]);
			}
		return e[1][n];
	}
};

int main() {
	int n;
	scanf("%d", &n);
	OBST obst;
	obst.read(n);
	printf("%.8lf\n", obst.cost(n));
}

C++: #include <cstdio>
#include <cctype>
#include <cfloat>
#include <vector>
using namespace std;

#define si static inline
#define gcu getchar_unlocked
si int in() {
	int c, n = 0;
	bool minus = false;
	if ((c = gcu()) == '-') minus = true; else ungetc(c, stdin);
	while ((c = gcu()) >= '0' && c <= '9') n = 10 * n + (c - '0');
	//return n; }
	return minus ? -n : n; }
si void scan(char *s) {while (!isspace(*s++ = gcu()));}
#define pcu putchar_unlocked
#define svo si void out
template <typename T>
svo(T n) {
	static char buf[20];
	char *p = buf;
	//if(n < 0) pcu('-'), n *= -1;
	if (!n) *p++ = '0';
	else while (n) *p++ = n % 10 + '0', n /= 10;
	while (p != buf) pcu(*--p); }
svo(const char *s){while(*s)pcu(*s++);}
svo(char *s){while(*s)pcu(*s++);}
svo(char c){pcu(c);}
template <typename T>
//svo(vector<T> &v){for(T &x:v)out(' '),out(x);out('\n');}
svo(vector<T> &v){for(T &x:v)out(&x == &v[0]?"":" "),out(x);out('\n');}
template <typename head, typename... tail>
svo(head&& h, tail&&... t){out(h);out(move(t)...);}
#undef svo
#undef si

#define v vector

struct OBST {
	typedef vector<double> vd;
	vd p, q;
	v<vd> e, w;

	void read(int n) {
		p.resize(n + 1);
		q.resize(n + 1);
		for (int i = 1; i <= n; i++)
			scanf("%lf", &p[i]);
		for (int i = 0; i <= n; i++)
			scanf("%lf", &q[i]);
	}

	double cost(int n) {
		e = v<vd>(n + 2, vd(n + 1));
		w = v<vd>(n + 2, vd(n + 1));
		for (int i = 0; i <= n; i++) {
			e[i + 1][i] = q[i];
			w[i + 1][i] = q[i];
		}
		for (int l = 1; l <= n; l++)
			for (int i = 1; i <= n - l + 1; i++) {
				int j = i + l - 1;
				e[i][j] = DBL_MAX;
				w[i][j] = w[i][j - 1] + p[j] + q[j];
				for (int r = i; r <= j; r++)
					e[i][j] = min(e[i][j], e[i][r - 1] + e[r + 1][j] + w[i][j]);
			}
		return e[1][n];
	}
};

int main() {
	int n = in();
	OBST obst;
	obst.read(n);
	printf("%.8lf\n", obst.cost(n));
}

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 <stdio.h>
#define MAX 501
using namespace std;

int main(int argc, char *argv[])
{
    int n;
    scanf("%d", &n);
    double p[MAX], q[MAX];
    p[0] = -1;
    for (int i = 1; i <= n; i++)
    {
        scanf("%lf", &p[i]);
    }
    for (int i = 0; i < n + 1; i++)
    {
        scanf("%lf", &q[i]);
    }

//    const int n = 5;
//      double p[n + 1] = {-1,0.15,0.1,0.05,0.1,0.2};
//     double q[n + 1] = {0.05,0.1,0.05,0.05,0.05,0.1};

    double e[MAX][MAX] = {0};
    double w[MAX][MAX] = {0};
    for (int i = 1; i <= n + 1; i++)
    {
        e[i][i - 1] = q[i - 1];
        w[i][i - 1] = q[i - 1];
    }

    int j = 0;
    for (int l = 1; l <= n; l++)
    {
        for (int i = 1; i <= n - l + 1; i++)
        {
            j = i + l - 1;
            e[i][j] = (1 << 21);
            w[i][j] = w[i][j - 1] + p[j] + q[j];
            for (int r = i; r <= j; r++)
            {
                double t = e[i][r - 1] + e[r + 1][j] + w[i][j];
                if (t < e[i][j])
                {
                    e[i][j] = t;
                }
            }
        }
    }
    printf("%lf", e[1][n]);

    return 0;
}

C++: #include <stdio.h>
#include <iostream>
#include <algorithm>

using namespace std;
#define N 501

int main(){
    int n;
    double p[N],q[N];
    double pSum[N][N],qSum[N][N];
    double d[N][N];
    double t;
    
    cin >> n;
    
    for(int i = 0;i < n;++i){
        cin >> p[i];
    }
    
    for(int i = 0;i < n + 1;++i){
        cin >> q[i];
        d[i][i] = q[i];
    }
    
     // p
    for(int i = 0;i < n;++i){
        pSum[i][i] = p[i];
        for(int j = i + 1;j < n;++j){
            pSum[i][j] = pSum[i][j - 1] + p[j];
        }
    }
    
    // q
    for(int i = 0;i < n + 1;++i){
        qSum[i][i] = q[i];
        for(int j = i + 1;j < n + 1;++j){
            qSum[i][j] = qSum[i][j - 1] + q[j];
        }
    }
    
    for(int i = 1;i < n + 1;++i){
        for(int j = 0;j < (n + 1) - i;++j){
            d[j][j + i] = __DBL_MAX__;
            for(int k = 0;k < i;++k){
                t = d[j][j + k] + d[j + k + 1][j + i] + pSum[j][j + i - 1] + qSum[j][j + i];
                d[j][j + i] = min(d[j][j + i], t);
            }
        }
    }
    
    printf("%.8lf\n",d[0][n]);
    
    return 0;
}