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