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;
double P[505],Q[505],dp[505][505],S[505][505],a1,a2;
int n,i,j,k,m;
int main(){
	cin>>n;
	for(i=1;i<=n;i++)scanf("%lf",&P[i]);
	for(i=0;i<=n;i++)scanf("%lf",&Q[i]);
	for(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];
	}
	for(k=1;k<n;k++)
		for(i=1;i<=n-k;i++){
			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(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>
#include <iomanip>
#include <algorithm>
using namespace std;

static const int MAX = 500;
double p[MAX + 1];
double q[MAX + 1];
double w[MAX + 2][MAX + 2];
double e[MAX + 2][MAX + 2];
double r[MAX + 1][MAX + 1];

int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        cin >> p[i];
    }
    for (int i = 0; i <= n; ++i)
    {
        cin >> q[i];
    }
    for (int i = 1; i != n + 2; ++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] = (1 << 21);
            w[i][j] = w[i][j-1] + p[j] + q[j];
            for (int k = i; k <= j; ++k)
            {
                double t = e[i][k-1] + e[k+1][j] + w[i][j];
                if (t < e[i][j])
                {
                    e[i][j] = t;
                    r[i][j] = k;
                }
            }
        }
    }
    cout << fixed << setprecision(8) << e[1][n] << endl;
    return 0;
}

C++: #include<stdio.h>
#include<iostream>
#include<algorithm>

#define N 501

using namespace std;

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) {
        //p[0]には代入しない
        //標準入力から探索確率を取得
        cin >> p[i];
    }
    
    for(int i = 0; i < n + 1; ++i) {
        //標準入力からダミーキーで探索終了する確率を取得
        cin >> q[i];
        
        //行列dの対角成分としてq[i]を格納
        d[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 < (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<iostream>
#include<vector>
#include<stdio.h>
using namespace std;

static const int INFTY = 20001;

double w[510][510];
double e[510][510];
int root[510][510];

int main(){

    int n;
    double P, Q, t; //グローバル変数にする必要がある
    vector<double> p, q;
    
    //入力処理
    cin >> n;
    p.push_back(0);
    for(int i=0; i<n; i++){
        cin >> P;
        p.push_back(P); 
    }
    for(int i=0; i<n+1; i++){
        cin >> Q;
        q.push_back(Q);
    }

    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] = 20001;
            w[i][j] = w[i][j-1] + p[j] + q[j];
            for(int k=i; k<=j; k++){
                t = e[i][k-1] + e[k+1][j] + w[i][j];    //期待値
                if(t < e[i][j]){    //最小値を探す
                    e[i][j] = t;
                    root[i][j] = k;
                }
            }
        }
    }
    printf("%.8lf\n", e[1][n]);
    return 0;
}

C++: #include <cstdio>
#include <algorithm>

#define N 500
int main(){
    int n;
    std::scanf("%d", &n);

    float p[N + 1];
    float q[N + 1];
    p[0] = 0.f;
    for(int i = 1; i <= n; ++i){
        std::scanf("%f", &p[i]);
    }
    for(int i = 0; i <= n; ++i){
        std::scanf("%f", &q[i]);
    }
    float a[N + 2][N + 2];
    float c[N + 2][N + 2];
    a[1][0] = q[0];
    c[1][0] = q[0];
    for(int i = 1; i <= n; ++i){
        a[i+1][i] = q[i];
        c[i+1][i] = q[i];
        a[i][i] = p[i] + q[i-1] + q[i];
        c[i][i] = p[i] + 2 * (q[i-1] + q[i]);
    }

    for(int l = 2; l <= n; ++l){
        for(int i = 1; i <= n - l + 1; ++i){
            int j = i + l - 1;
            a[i][j] = a[i][j-1] + a[i+1][j] - a[i+1][j-1];
            c[i][j] = 1000.f;
            for(int k = i; k <= j; ++k){
                c[i][j] = std::min(c[i][j], c[i][k-1] + a[i][k-1] + c[k+1][j] + a[k+1][j] + p[k]);
            }
        }
    }

    std::printf("%f\n", c[1][n]);
}

C++: #include<iostream>
#include<cmath>
#include<iomanip>
using namespace std;
#define MAX 550
#define INF (1e100)

int n;
double p[MAX], q[MAX];
int temp[MAX][MAX];
double temp2[MAX][MAX], temp3[MAX][MAX];

// double fuga(int a, int b, int count){
	// if(a>b)return 0;
	// double ans = count*p[temp[a][b]];
	// ans += fuga(a,temp[a][b]-1,count+1);
	// ans += fuga(temp[a][b]+1,b,count+1);
	// if(a == temp[a][b]) ans += q[a-1]*(count+1);
	// if(b == temp[a][b]) ans += q[b]*(count+1);
	
	// return ans;
// }
double fuga(int a, int b, int count){
	if(a>b)return 0;
	double ans = p[temp[a][b]];
	temp3[a][b] = 0;
	if(a <= temp[a][b]-1)ans += temp2[a][temp[a][b]-1]+temp3[a][temp[a][b]-1];
	if(temp[a][b]+1 <= b)ans += temp2[temp[a][b]+1][b]+temp3[temp[a][b]+1][b];
	temp3[a][b] = temp3[a][temp[a][b]-1] + temp3[temp[a][b]+1][b] + p[temp[a][b]];
	if(a==temp[a][b]) {temp3[a][b] += q[a-1]; ans += q[a-1]*2;}
	if(b==temp[a][b]) {temp3[a][b] += q[b];   ans += q[b]*2;}
	return ans;
}

void hoge(int a, int b){
	double t, mi = INF;
	int ti = a;

	for(int i = a; i <= b; i++){
		temp[a][b] = i;
		if((t = fuga(a,b,1)) < mi){
			mi = t;
			ti = i;
		}
	}
	temp[a][b] = ti;
	temp2[a][b] = fuga(a,b,1);
	// temp2[a][b] = mi;
}

double solve(){
	
	for(int i = 1; i < n; i++){
		for(int j = 1; j+i <= n; j++){
			hoge(j,j+i);
		}
	}
}

void print(){
	for(int i = 1; i <= n; i++){
		// for(int j = 1; j < i; j++){
			// cout<<"\t\t";
		// }
		for(int j = 1; j <= n; j++){
			// cout<<fuga(i,j,1)<<"\t\t";
			// cout<<temp[i][j]<<" "<<fuga(i,j,1)<<"\t\t";
			cout<<temp[i][j]<<" "<<temp2[i][j]<<"\t\t";
		}
		cout<<endl;
	}
}

int main(){
	cout<<fixed<<setprecision(5);
	cin>>n;
	
	for(int i = 1; i <= n; i++){
		cin>>p[i];
		temp[i][i] = i;
		temp3[i][i] = p[i];
		temp2[i][i] = p[i];
	}
	for(int i = 0; i <= n; i++){
		cin>>q[i];
		temp2[i][i] += q[i]*2;
		temp2[i+1][i+1] += q[i]*2;
		temp3[i][i] += q[i];
		temp3[i+1][i+1] += q[i];
	}
	solve();
	// print();
	cout<<fuga(1,n,1)<<endl;
	
	return 0;
}