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