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 <iostream>
#include <algorithm>
#include <stdio.h>
using namespace std;
double e[1001][51001];
double optimalBST(double p[],double q[],int n){
    double w[1001][1001];
    for(int i=1;i<=n+1;i++){
        e[i][i-1]=q[i-1];
        w[i][i-1]=q[i-1];
    }
    for(int l=1;l<=n;l++){
        for(int i=1;i<=n-l+1;i++){
            int j=i+l-1;
            e[i][j]=1000.0;
            w[i][j]=w[i][j-1]+p[j]+q[j];
            for(int r=i;r<=j;r++){
                double t=e[i][r-1]+e[r+1][j]+w[i][j];
                if(t<e[i][j]){
                    e[i][j]=t;
                }
            }
        }
    }
    return e[1][n];
}
int main(){
    int n;
    double p[1001],q[1001];
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>p[i];
    }
    for(int i=0;i<=n;i++){
        cin>>q[i];
    }
    

    printf("%.8lf\n", optimalBST(p,q,n)); 

    return 0;
}

C++: #include <bits/stdc++.h>
using namespace std;
double P[505],Q[505],dp[505][505],S[505][505];
int main()
{
	int n; cin>>n;
	for(int i=1;i<=n;i++) scanf("%lf",&P[i]);
	for(int i=0;i<=n;i++) scanf("%lf",&Q[i]);
	for(int i=1;i<=n;i++){
		dp[i][i] = P[i]+2*(Q[i-1]+Q[i]);
		S[i][i] = P[i]+Q[i-1]+Q[i];
	}
	double a1,a2;
	for(int k=1;k<n;k++)
		for(int i=1;i<=n-k;i++){
			int j = i+k;
			S[i][j] = S[i][j-1]+P[j]+Q[j];
			a1 = S[i][j]+Q[i-1]+dp[i+1][j];
			a2 = S[i][j]+Q[j]+dp[i][j-1];
			dp[i][j] = min(a1,a2);
			for(int m=i+1;m<j;m++)
				dp[i][j] = min(dp[i][j],S[i][j]+dp[i][m-1]+dp[m+1][j]);
		}
	printf("%.8lf\n",dp[1][n]);
	return 0;
}

C++: #include<iostream>
#define INF 1<<20
using namespace std;
int main() {
  int n; cin >> n;
  double p[510], q[510];
  for (int i = 1; i <= n; ++i) cin >> p[i];
  for (int i = 0; i < n + 1; ++i) cin >> q[i];
  double sump[501] = {}, sumq[501] = {}, dp[510][510] = {};
  for (int i = 1; i <= n; ++i) sump[i] = sump[i - 1] + p[i];
  sumq[0] = q[0];
  for (int i = 1; i <= n; ++i) sumq[i] = sumq[i - 1] + q[i];
  for (int i = 1; i <= n; ++i)
    for (int j = i; j <= n; ++j) dp[i][j] = INF;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n - i + 1; ++j) {
      int x = i + j - 1;
      for (int k = j; k <= x; ++k) {
	double sum = sump[x] - sump[j - 1]+sumq[x];
	if (j >= 2) sum -= sumq[j - 2];
	if (dp[j][x] > sum + dp[j][k - 1] - p[k] + dp[k + 1][x]) dp[j][x] = sum + dp[j][k - 1] - p[k] + dp[k + 1][x];
      }
    }
  }
  cout << dp[1][n] + 1 << endl;
  return 0;
}

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

int main()
{
    int n;
    cin >> n;
    double p[n];
    double q[n + 1];
    double dp[n + 1][n + 1];
    for (int i = 0; i < n; i++)
        cin >> p[i];
    for (int i = 0; i <= n; i++)
    {
        cin >> q[i];
        dp[i][i] = q[i];
    }
    double pSum[n][n];
    for (int i = 0; i < n; i++)
    {
        pSum[i][i] = p[i];
        for (int j = i + 1; j < n; j++)
            pSum[i][j] = pSum[i][j - 1] + p[j];
    }
    double qSum[n + 1][n + 1];
    for (int i = 0; i < n + 1; i++)
    {
        qSum[i][i] = q[i];
        for (int j = i + 1; j < n + 1; j++)
            qSum[i][j] = qSum[i][j - 1] + q[j];
    }
    for (int i = 1; i < n + 1; i++)
    {
        for (int j = 0; j < n + 1 - i; j++)
        {
            dp[j][j + i] = 1145141919;
            for (int k = 0; k < i; k++)
            {
                double tmp = dp[j][j + k] + dp[j + k + 1][j + i] + pSum[j][j + i - 1] + qSum[j][j + i];
                dp[j][j + i] = min(dp[j][j + i], tmp);
            }
        }
    }
    printf("%.8f\n", dp[0][n]);
}

C++: #include<bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i) 
#define PI acos(-1)

using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using LP = pair<ll, ll>;

template<class T> inline bool chmax(T& a, T b) {if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) {if (a > b) { a = b; return true; } return false; }

#define INF 1001001

double dpRec(int l, int r, vector<vector<double>>& dp, vector<vector<int>>& key, vector<double> sump, vector<double> sumq) {
    if (dp[l][r] != INF) return dp[l][r];
    if (l > r) {
        dp[l][r] = sumq[r + 1] - sumq[l - 1];
        return dp[l][r];
    }

    double s = sump[r] - sump[l - 1] + sumq[r + 1] - sumq[l - 1];

    if (chmin(dp[l][r], dpRec(l, l - 1, dp, key, sump, sumq) + dpRec(l + 1, r, dp, key, sump, sumq) + s)) {
        key[l][r] = l;
    }
    if (l == r) return dp[l][r];
    
    if (chmin(dp[l][r], dpRec(l, r - 1, dp, key, sump, sumq) + dpRec(r + 1, r, dp, key, sump, sumq) + s)) {
        key[l][r] = r;
    }

    for (int i = key[l][r - 1]; i <= key[l + 1][r]; ++i) {
        if (chmin(dp[l][r], dpRec(l, i - 1, dp, key, sump, sumq) + dpRec(i + 1, r, dp, key, sump, sumq) + s)) {
            key[l][r] = i;
        }
    }
    return dp[l][r];
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n;
    cin>>n;
    vector<double> ps(n), sump(n + 1), qs(n + 1), sumq(n + 2);
    rep(i, n) {
        cin>>ps[i];
        sump[i + 1] = sump[i] + ps[i];
    }
    rep(i, n + 1) {
        cin>>qs[i];
        sumq[i + 1] = sumq[i] + qs[i];
    }

    vector<vector<double>> dp(n + 2, vector<double>(n + 2, INF));
    vector<vector<int>> key(n + 2, vector<int>(n + 2, INF));
    double ans = dpRec(1, n, dp, key, sump, sumq);
    printf("%.10f\n", ans);
}