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 <bits/stdc++.h>
using namespace std;

#define INF 1e9
vector<double> p, q;

double memo[504][504];
double psum[504];
double qsum[504];

// [l,r)の木を構成した時に含まれる p,qの和
double sum(int l, int r) {
  assert(r > l);
  return psum[r] - psum[l] + qsum[r] - qsum[l - 1];
}

// [l, r)の区間について木にした時のコスト期待値
double dfs(int l, int r) {
  // 1個の時
  if (l + 1 == r) {
    // 今の深さ × p, 次の深さ x q (ダミーノード分)
    return p[l] + 2 * (q[l - 1] + q[l]);
  }
  if (memo[l][r] != -1) return memo[l][r];

  double ret = INF;
  // m を根にする分け方
  for (int m = l; m < r; m++) {
    double root, left, right;
    // 根の分
    root  = p[m];
    // 左部分木
    if (l == m) left  = 2 * q[l - 1];          // 端なのでダミー
    else        left  = dfs(l, m) + sum(l, m); // [l,m)の木の解 + l~mまでの和([l,m)の木の深さを1つ増やす)

    // 右部分木
    if (r - 1 == m) right = 2 * q[r - 1];      // 端なのでダミー
    else            right = dfs(m + 1, r) + sum(m + 1, r);
    
    ret = min(ret, root + left + right);
  }
  return memo[l][r] = ret;
}

int main(void) {
  int n;
  cin >> n;
  p = vector<double>(n + 1);
  q = vector<double>(n + 1);
  for (int i = 0; i < n; i++) {
    cin >> p[i + 1];
    psum[i + 2] += psum[i + 1] + p[i + 1];
  }
  for (int i = 0; i < n + 1; i++) {
    cin >> q[i];
    qsum[i + 1] += qsum[i] + q[i];
  }

  for (int i = 0; i < 502; i++) for (int j = 0; j < 502; j++) {
    memo[i][j] = -1;
  }

  cout << fixed << setprecision(10) << dfs(1, n + 1) << endl;

  return 0;
}

C++: #include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

float OptimalBSTree(vector<float> p, vector<float> q){
	int n = p.size();

	vector< vector<float> > psum(n, vector<float>(n, 0));
	for (int i = 0; i < n; i++){
		for (int j = 0; j < n - i; j++){
			if (i == 0){
				psum[j][j] = p[j];
			}
			else{
				psum[j][j + i] = psum[j][j + i - 1] + p[j + i];
			}
		}
	}
	vector< vector<float> > qsum(n + 1, vector<float>(n + 1, 0));
	for (int i = 0; i < n + 1; i++){
		for (int j = 0; j < n + 1 - i; j++){
			if (i == 0){
				qsum[j][j] = q[j];
			}
			else{
				qsum[j][j + i] = qsum[j][j + i - 1] + q[j + i];
			}
		}
	}

	float et;
	vector< vector<float> > table(n + 1, vector<float>(n + 1, 0));
	for (int i = 0; i < n + 1; i++){
		for (int j = 0; j < n + 1 - i; j++){
			if (i == 0){
				table[j][j] = q[j];
			}
			else{
				float min;
				for (int k = 0; k < i; k++){
					et = table[j][j + k] + table[j + k + 1][j + i] + psum[j][i + j - 1] + qsum[j][i + j];
					if (k == 0 || et < min) min = et;
				}
				table[j][j + i] = min;
			}
		}
	}
	return table[0][n];
}

int main(){
	int n;
	scanf("%d", &n);
	vector<float> p(n), q(n + 1);
	for (int i = 0; i < n; i++){
		scanf("%f", &p[i]);
	}
	for (int i = 0; i < n + 1; i++){
		scanf("%f", &q[i]);
	}
	printf("%f\n", OptimalBSTree(p, q));

	return 0;
}

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