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