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 <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>
#include <climits>
#include <cassert>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <string>
#include <list>
#include <bitset>
#include <vector>
using namespace std;

#define I64d_OJ

//#ifdef I64d_OJ
//#define LL __int64
//#endif // I64d_OJ
#ifdef I64d_OJ
#define LL long long
#endif // I64d_OJ

typedef unsigned LL ULL;
typedef unsigned uint;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
typedef pair<LL,LL> pLL;
typedef vector<int> vi;

inline LL read(){
    LL x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=-f; ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}

#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define ls rt<<1
#define rs rt<<1|1
#define MID(a,b) (((LL)(a)+(LL)(b))>>1)
#define absx(a) ((a)<0?-(a):(a))
#define MK(a,b) make_pair(a,b)
#define PB(a) push_back(a)
#define lowbit(x) ((x)&-(x))

template< typename T >
inline void Max(T &a,T &b){if(a<b) a=b;}
template< typename T>
inline void Min(T &a,T &b){if(a>b) a=b;}

const double pi=(double)acos(-1.0);
const double eps=(double)1e-10;
const int INF = (int) 0x3f3f3f3f;
const int MOD = (int) 1e9+7;
const int MAXN =(int) 5e2+10;
const int MAXM = (int) 2e5+10;
const int sigma_size = (int) 26;

///--------------------START-------------------------
int n;
double p[MAXN],q[MAXN];
double f[MAXN][MAXN];
double sump[MAXN],sumq[MAXN];

void work(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%lf",&p[i]);
    for(int i=0;i<=n;i++) scanf("%lf",&q[i]);
    sumq[0]=q[0];
    for(int i=1;i<=n;i++) sump[i]=sump[i-1]+p[i],sumq[i]=sumq[i-1]+q[i];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            f[i][j]=1.0*INF;
            if(j<i) f[i][j]=0.0;
        }
    }
    for(int len=1;len<=n;len++){
        for(int i=1;i+len-1<=n;i++){
            int j=i+len-1;
            for(int k=i;k<=j;k++){
                double tsum=sump[j]-sump[i-1];
                if(i==1) tsum+=sumq[j];
                else tsum+=sumq[j]-sumq[i-2];
                f[i][j]=min(f[i][j],tsum-p[k]+f[i][k-1]+f[k+1][j]);
            }
        }
    }
    printf("%.8lf\n",f[1][n]+sump[n]+sumq[n]);
}
/*
5
0.1500 0.1000 0.0500 0.1000 0.2000
0.0500 0.1000 0.0500 0.0500 0.0500 0.1000

7
0.0400 0.0600 0.0800 0.0200 0.1000 0.1200 0.1400
0.0600 0.0600 0.0600 0.0600 0.0500 0.0500 0.0500 0.0500
*/
///--------------------END-------------------------
int main(){
#ifdef NNever
//freopen("data.in","r",stdin);
///freopen("out.txt","w",stdout);
#endif // NNever
    work();
    return 0;
}

C++: #include<bits/stdc++.h>
using namespace std;

#define MAX 1010
#define INF (1<<30)

double costSum[MAX][MAX],optCost[MAX][MAX];

//{{{ Functions
void ComputeOptCost(int i, int j){
	optCost[i][j]=INF;
	for(int k=i; k<=j; k++){
		optCost[i][j]=min(optCost[i][k-1]+optCost[k+1][j], optCost[i][j]);
	}
	optCost[i][j]+=costSum[i][j];
}
//}}}

int main(){
	int n;	cin>>n;
	vector<double> P(n+1),Q(n+1);
	for(int i=1;i<=n;i++)cin>>P[i];
	for(int i=0;i<=n;i++)cin>>Q[i];

	/*
		costSum[i][j]:
			(i: 1,2,~,n)

		(j==i-1) Q[i-1]
		(else) costSum[i][j-1]+ P[j]+Q[j]
	*/

	//costSum の初期化
	for(int i=1; i<=n; i++){
		costSum[i][i-1]=Q[i-1];
		for(int j=i; j<=n; j++){
			costSum[i][j]=costSum[i][j-1] + P[j]+Q[j];
		}
	}

	for(int i=1;i<=n+1;i++)optCost[i][i-1]=Q[i-1];
	for(int d=0; d<=n-1; d++){
		for(int i=1;i<=n-d;i++){
			ComputeOptCost(i,i+d);
		}
	}
	//cout<<optCost[1][1]<<endl;
	//cout<<optCost[1][n]<<endl;
	printf("%.8lf\n",optCost[1][n]);

	return 0;
}