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 <cstdio>
#include <algorithm>

#define N 500
int main(){
    int n;
    std::scanf("%d", &n);

    float p[N + 1];
    float q[N + 1];
    p[0] = 0.f;
    for(int i = 1; i <= n; ++i){
        std::scanf("%f", &p[i]);
    }
    for(int i = 0; i <= n; ++i){
        std::scanf("%f", &q[i]);
    }
    float a[N + 2][N + 2];
    float c[N + 2][N + 2];
    a[1][0] = q[0];
    c[1][0] = q[0];
    for(int i = 1; i <= n; ++i){
        a[i+1][i] = q[i];
        c[i+1][i] = q[i];
        a[i][i] = p[i] + q[i-1] + q[i];
        c[i][i] = p[i] + 2 * (q[i-1] + q[i]);
    }

    for(int l = 2; l <= n; ++l){
        for(int i = 1; i <= n - l + 1; ++i){
            int j = i + l - 1;
            a[i][j] = a[i][j-1] + a[i+1][j] - a[i+1][j-1];
            c[i][j] = 1000.f;
            for(int k = i; k <= j; ++k){
                c[i][j] = std::min(c[i][j], c[i][k-1] + a[i][k-1] + c[k+1][j] + a[k+1][j] + p[k]);
            }
        }
    }

    std::printf("%f\n", c[1][n]);
}

C++: #include<iostream>
#include<cmath>
#include<iomanip>
using namespace std;
#define MAX 550
#define INF (1e100)

int n;
double p[MAX], q[MAX];
int temp[MAX][MAX];
double temp2[MAX][MAX], temp3[MAX][MAX];

// double fuga(int a, int b, int count){
	// if(a>b)return 0;
	// double ans = count*p[temp[a][b]];
	// ans += fuga(a,temp[a][b]-1,count+1);
	// ans += fuga(temp[a][b]+1,b,count+1);
	// if(a == temp[a][b]) ans += q[a-1]*(count+1);
	// if(b == temp[a][b]) ans += q[b]*(count+1);
	
	// return ans;
// }
double fuga(int a, int b, int count){
	if(a>b)return 0;
	double ans = p[temp[a][b]];
	temp3[a][b] = 0;
	if(a <= temp[a][b]-1)ans += temp2[a][temp[a][b]-1]+temp3[a][temp[a][b]-1];
	if(temp[a][b]+1 <= b)ans += temp2[temp[a][b]+1][b]+temp3[temp[a][b]+1][b];
	temp3[a][b] = temp3[a][temp[a][b]-1] + temp3[temp[a][b]+1][b] + p[temp[a][b]];
	if(a==temp[a][b]) {temp3[a][b] += q[a-1]; ans += q[a-1]*2;}
	if(b==temp[a][b]) {temp3[a][b] += q[b];   ans += q[b]*2;}
	return ans;
}

void hoge(int a, int b){
	double t, mi = INF;
	int ti = a;

	for(int i = a; i <= b; i++){
		temp[a][b] = i;
		if((t = fuga(a,b,1)) < mi){
			mi = t;
			ti = i;
		}
	}
	temp[a][b] = ti;
	temp2[a][b] = fuga(a,b,1);
	// temp2[a][b] = mi;
}

double solve(){
	
	for(int i = 1; i < n; i++){
		for(int j = 1; j+i <= n; j++){
			hoge(j,j+i);
		}
	}
}

void print(){
	for(int i = 1; i <= n; i++){
		// for(int j = 1; j < i; j++){
			// cout<<"\t\t";
		// }
		for(int j = 1; j <= n; j++){
			// cout<<fuga(i,j,1)<<"\t\t";
			// cout<<temp[i][j]<<" "<<fuga(i,j,1)<<"\t\t";
			cout<<temp[i][j]<<" "<<temp2[i][j]<<"\t\t";
		}
		cout<<endl;
	}
}

int main(){
	cout<<fixed<<setprecision(5);
	cin>>n;
	
	for(int i = 1; i <= n; i++){
		cin>>p[i];
		temp[i][i] = i;
		temp3[i][i] = p[i];
		temp2[i][i] = p[i];
	}
	for(int i = 0; i <= n; i++){
		cin>>q[i];
		temp2[i][i] += q[i]*2;
		temp2[i+1][i+1] += q[i]*2;
		temp3[i][i] += q[i];
		temp3[i+1][i+1] += q[i];
	}
	solve();
	// print();
	cout<<fuga(1,n,1)<<endl;
	
	return 0;
}

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