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 <stdio.h>
#include <iostream>
#include <algorithm>

using namespace std;
#define N 501

int main(){
    int n;
    double p[N],q[N];
    double pSum[N][N],qSum[N][N];
    double d[N][N];
    double t;
    
    cin >> n;
    
    for(int i = 0;i < n;++i){
        cin >> p[i];
    }
    
    for(int i = 0;i < n + 1;++i){
        cin >> q[i];
        d[i][i] = q[i];
    }
    
     // p
    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];
        }
    }
    
    // q
    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){
            d[j][j + i] = __DBL_MAX__;
            for(int k = 0;k < i;++k){
                t = d[j][j + k] + d[j + k + 1][j + i] + pSum[j][j + i - 1] + qSum[j][j + i];
                d[j][j + i] = min(d[j][j + i], t);
            }
        }
    }
    
    printf("%.8lf\n",d[0][n]);
    
    return 0;
}

C++: #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define EPS (1e-7)
#define INF (1e9)
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
const double PI = acos(-1);
const ll MOD = 1000000007;
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;
}

int main() {
  int N; cin >> N;
  vector<double> p(N),q(N+1);
  rep(i,N) cin >> p[i];
  rep(i,N+1) cin >> q[i];

  vector<vector<double>> dp(N+1, vector<double>(N+1,INF)); 
  vector<vector<int>> key(N+1, vector<int>(N+1));
  rep(i,N+1) {
    dp[i][i] = q[i];
    key[i][i] = i;
  }
  vector<double> sumw(N+2),sump(N+1);
  rep(i,N+1) {
    if (i == 0) {
      sumw[1] = q[0];
      sump[1] = p[0];
    } else {
      sumw[i+1] = sumw[i] + q[i];
      if (i != N)sump[i+1] = sump[i] + p[i];
    }
  }

  for (int k = 1; k < N+1; k++) {
    for (int i = 0; i < N+1-k; i++) {
      for (int j = key[i][i+k-1]; j <= min(key[i+1][i+k],N-1); j++) {
        if (chmin(dp[i][i+k],dp[i][j] + dp[j+1][i+k])) key[i][i+k] = j;
      }
      dp[i][i+k] += (sumw[i+k+1] - sumw[i] + sump[i+k] - sump[i]);
    }
  }
  
  cout << fixed << setprecision(10) << dp[0][N] << endl;
}

C++: #include<bits/stdc++.h>

using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)

typedef long long ll;
typedef pair<int, int> P;

#define MAX 100005
#define INF INT_MAX

vector<double> p, q;
vector< vector<double> > memo1; // 部分木の値(深さで重みづけ済み)
vector< vector<double> > memo2; // 部分木の値(深さで重みづけなし)

double obst(int l, int r)
{
    if (memo1[l][r]) return memo1[l][r];
    if (l == r) {
        memo1[l][r] = memo2[l][r] = q[l];
        return q[l];
    }

    double res = DBL_MAX;

    rep(i,r-l) {
        double lt = obst(l,l+i);
        double rt = obst(l+i+1,r);
        double rowt = p[l+i+1] + memo2[l][l+i] + memo2[l+i+1][r];
        double mg = rowt + rt + lt;
        if (mg < res) {
            res = mg;
            memo2[l][r] = rowt;
        }
    }

    memo1[l][r] = res;
    return res;
}

int main(int, char**)
{
    int n;
    cin >> n;
    p.assign(n+1, 0);
    q.assign(n+1, 0);
    memo1.assign(n+1, vector<double>(n+1, 0));
    memo2.assign(n+1, vector<double>(n+1, 0));

    rep(i,n) cin >> p[i+1];
    rep(i,n+1) cin >> q[i];

    printf("%.10f",obst(0, n));  
    return 0;
}

C++: import java.io.PrintWriter
import java.util.*

data class PE(var p: Double, var e: Double)
data class Node(var center: PE, var left: PE, var right: PE, var lNode: Node?, var rNode: Node?) : Comparable<Node> {
    override fun compareTo(other: Node): Int {
        val a = center.e + center.p
        val o = other.center.e + other.center.p
        return if (a == o) 0
        else if( a < o ) -1
        else 1
    }
}

fun main(args: Array<String>) = with(PrintWriter(System.out)) {
    val n = readLine()!!.toInt()
    val p = readLine()!!.trim().split(' ').map { it.toDouble() }
    val q = readLine()!!.trim().split(' ').map { it.toDouble() }

    val list = mutableListOf<Node>()
    for (i in 0 until n) {
        val c = p[i]
        val l = q[i]
        val r = q[i+1]
        list.add(Node(PE(c+l+r, c+(l+r)*2), PE(l, l), PE(r, r), null, null))
    }

    if ( n == 1 ) {
        print(list[0].center.e)
        flush()
        return
    }

    list[0].rNode = list[1]
    list[n-1].lNode = list[n-2]
    for (i in 1 until n-1) {
        list[i].lNode = list[i-1]
        list[i].rNode = list[i+1]
    }

    // pop min e+p
    val queue = PriorityQueue<Node>(n)
    queue.addAll(list)

    while (queue.size != 1) {
        val minNode = queue.poll()

        if (minNode.rNode != null) {
            val rNode = minNode.rNode!!
            queue.remove(rNode)
            rNode.center.p = rNode.center.p - rNode.left.p + minNode.center.p
            rNode.center.e = rNode.center.e - rNode.left.e - rNode.left.p + minNode.center.e + minNode.center.p
            rNode.left = minNode.center
            rNode.lNode = minNode.lNode
            queue.add(rNode)
        }

        if (minNode.lNode != null) {
            val lNode = minNode.lNode!!
            queue.remove(lNode)
            lNode.center.p = lNode.center.p - lNode.right.p + minNode.center.p
            lNode.center.e = lNode.center.e - lNode.right.e - lNode.right.p + minNode.center.e + minNode.center.p
            lNode.right = minNode.center
            lNode.rNode = minNode.rNode
            queue.add(lNode)
        }
    }

    val minNode = queue.poll()
    println(minNode.center.e)
    flush()
}

C++: #include<iostream>
#include<algorithm>
#include<cfloat>
using namespace std;
int main(){
        int n;
        cin>>n;
        double p[n], q[n+1];
        for(int i=0;i<n;i++) cin>>p[i];
        for(int i=0;i<n+1;i++) cin>>q[i];

        double dp[n+1][n+1];
        double psum[n][n];
        double qsum[n+1][n+1];
        for(int i=0;i<n+1;i++) dp[i][i] = q[i];
        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];
                }
        }
        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+i<n+1;j++){
                        dp[j][j+i] = DBL_MAX;
                        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);
                        }
                }
        }
        cout<<dp[0][n]<<endl;

        return 0;
}