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 <iostream>
#include <iomanip>
#include <vector>

using namespace std; 

int main(void) {
	int n;
	cin >> n;
	vector<double> p(n+1);
	p[0] = 1;
	for (int i = 0; i < n; ++i) {
		cin >> p[i+1];
	}
	vector<double> q(n+1);
	vector< vector<double> > sum(n+1,vector<double>(n+1));
	vector< vector<double> > dp(n+1,vector<double>(n+1,(1 << 28)));
	for (int i = 0; i < n+1; ++i) {
		cin >> q[i];
		if (i > 0) {
			dp[i][i] = p[i]+(2*(q[i-1]+q[i]));
			sum[i][i] = dp[i][i] - (q[i-1]+q[i]); 
		}
	}
	for (int i = 1; i < n+1; ++i) {
		for (int j = i+1; j < n+1; ++j) {
			sum[i][j] = sum[i][j-1] + sum[j][j] - q[j-1];
		}
	}
	double rc,left,right;
	for (int k = 2; k < n+1; ++k) {
		for (int i = 1; i < n-k+2; ++i) {
			for (int j = 0; j < k; ++j) {
				rc = dp[i+j][i+j];
				left = right = 0;
				if (j != 0) {
					rc -= 2*q[i+j-1];
					left += dp[i][i+j-1] + sum[i][i+j-1];
				}
				if (j != k-1) {
					rc -= 2*q[i+j];
					right += dp[i+j+1][i+k-1] + sum[i+j+1][i+k-1];
				}
				dp[i][i+k-1] = min(rc+left+right,dp[i][i+k-1]);
			}
		}
	}
	cout << setprecision(20) << fixed << dp[1][n] << endl;

	return 0;
}

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