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;
typedef long long ll;
typedef pair<ll, ll> l_l;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
//const ll mod = 1000000007;5
double dp[505][505];
int n;
double p[505];
double q[505];
double psum[505];
double qsum[505];

double search(int l, int r) {
    if(dp[l][r] != 0) return dp[l][r];
    if(l == r) {
        return dp[l][r] = 0;
    }
    dp[l][r] = 1e9;
    double total = qsum[r] - qsum[l-1] + psum[r] - psum[l];
    for(int x = l + 1; x <= r; x++) {
        double left = qsum[x-1] - qsum[l-1] + psum[x-1] - psum[l];
        double right = total - left - p[x];
        double now = (search(l, x - 1) + 1) * (left / total) + (search(x, r) + 1) * (right / total);
        dp[l][r] = min(dp[l][r], now);
    }
    return dp[l][r];
}

int main() {
    cout.precision(10);
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n;
    for(int i = 2; i <= n + 1; i++) cin >> p[i];
    for(int i = 1; i <= n + 1; i++) cin >> q[i];
    for(int i = 1; i <= n + 1; i++) psum[i] = psum[i-1] + p[i];
    for(int i = i; i <= n + 1; i++) qsum[i] = qsum[i-1] + q[i];
    cout << 1.0 + search(1, n+1) << endl;
    return 0;
}

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

using namespace std;
#define fordebug int hoge;cin>>hoge;
#define DEKAI 1000000007
#define INF (1<<28)
#define lp(i,n) for(int i=0;i<n;i++)
#define lps(i,j,n) for(int i=j;i<n;i++)
#define floot10 cout<<fixed<<setprecision(10);
#define int long long

double p[5000],q[5000],sump[5000],sumq[5000];
double memo[5000][5000];

signed main(){
	floot10;
	int n;
	cin>>n;
	lp(i,n) cin>>p[i+1];
	lp(i,n+1) cin>>q[i];
	sumq[0]=q[0];
	lp(i,n){
		sump[i+1]=sump[i]+p[i+1];
		sumq[i+1]=sumq[i]+q[i+1];
	}
	lps(i,1,n+1){
		lps(j,1,n+1){
			if(j>=i)memo[i][j]=INF;
			else memo[i][j]=0;
		}
	}
	lps(l,1,n+1){
		lps(i,1,n+2-l){
			int j=i+l-1;
			lps(k,i,j+1){
				double sum=sump[j]-sump[i-1];
				if(i==1) sum+=sumq[j];
				else{
					sum+=sumq[j]-sumq[i-2];
				}
				memo[i][j]=min(memo[i][j],sum-p[k]+memo[i][k-1]+memo[k+1][j]);
			}
		}
	}
	cout<<memo[1][n]+sump[n]+sumq[n]<<endl;
	return 0;
}

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

using Lint=long long;
const double INF=1e9;

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

   vector<double> sumP(N),sumQ(N+1);
   for(int i=0;i<N-1;i++) sumP[i+1]=sumP[i]+p[i];
   for(int i=0;i<N;i++) sumQ[i+1]=sumQ[i]+q[i];

   vector<vector<double>> dp(N+1,vector<double>(N+1,INF));
   for(int i=0;i<N;i++) dp[i][i+1]=0;
   for(int len=2;len<=N;len++){
      for(int l=0;l+len<=N;l++){
         int r=l+len;
         for(int m=l+1;m<r;m++){
            double cost=(sumQ[r]-sumQ[l])+(sumP[m-1]-sumP[l])+(sumP[r-1]-sumP[m]);
            dp[l][r]=min(dp[l][r],dp[l][m]+dp[m][r]+cost);
         }
      }
   }
   double ans=dp[0][N];
   ans+=accumulate(p.begin(),p.end(),0.0);
   ans+=accumulate(q.begin(),q.end(),0.0);
   cout<<fixed<<setprecision(10)<<ans<<endl;
   return 0;
}

C++: #include<iostream>
#include<algorithm>
using namespace std;
#define INFTY (1<<30)

int n;
double p[550], q[550], M[550][550], P[550][550];

void setP( void ) {
  for ( int i = 0; i < n + 1; i++ ) P[i][i] = q[i];
  for ( int i = 0; i < n; i++ ) {
    for ( int j = i + 1; j < n + 1; j++ ) P[i][j] = P[i][j - 1] + p[j] + q[j];
  }
}

void setM( void ) {
  for ( int i = 0; i < n + 1; i++ ) M[i][i] = q[i];
  for ( int l = 1; l < n + 1; l++ ) {
    for ( int i = 0; i < n - l + 1; i++ ) {
      int j = i + l;
      M[i][j] = INFTY;
      for ( int k = i + 1; k < j + 1; k++ ) {
        M[i][j] = min(M[i][j], M[i][k - 1] + M[k][j] + P[i][j]);
      }
    }
  }
}

int main() {
  cin >> n;
  for ( int i = 1; i < n + 1; i++ ) cin >> p[i];
  for ( int i = 0; i < n + 1; i++ ) cin >> q[i];
  
  setP();
  setM();

  cout << M[0][n] << endl;

  return 0;
}

C++: #include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, n) for (ll i = 0; i < n; ++i)
ll dx[4] = { 0, 1, 0, -1 };
ll dy[4] = { 1, 0, -1, 0 };
const ll INF = 1 << 21;
const ll MOD = 1e9 + 7;

const int N = 500;

double p[5000], q[5000], sump[5000], sumq[5000];
double memo[5000][5000];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    rep(i, n) { cin >> p[i + 1]; }
    rep(i, n + 1) { cin >> q[i]; }
    sumq[0] = q[0];

    rep(i, n)
    {
        sump[i + 1] = sump[i] + p[i + 1];
        sumq[i + 1] = sumq[i] + q[i + 1];
    }

    for (int i = 1; i < n + 1; ++i) {
        for (int j = 1; j < n + 1; ++j) {
            if (j >= i) {
                memo[i][j] = INF;
            } else {
                memo[i][j] = 0;
            }
        }
    }

    for (int l = 1; l < n + 1; ++l) {
        for (int i = 1; i < n + 2 - l; ++i) {
            int j = i + l - 1;
            for (int k = i; k < j + 1; ++k) {
                double sum = sump[j] - sump[i - 1];
                if (i == 1) {
                    sum += sumq[j];
                } else {
                    sum += sumq[j] - sumq[i - 2];
                }
                memo[i][j] = min(memo[i][j], sum - p[k] + memo[i][k - 1] + memo[k + 1][j]);
            }
        }
    }
    cout << memo[1][n] + sump[n] + sumq[n] << endl;
    return 0;
}

C++: #include <iostream>
#include <cfloat>

double min(double x, double y)
{
	return x>y ? y : x;
}

int main()
{
	std::string strn; getline(std::cin, strn);
	int n = std::stoi(strn);
	
	double *p = new double[n];
	double *q = new double[n+1];
	
	for (int i=0; i<n; i++) std::cin >> p[i];  // p[0], p[1], ... , p[n-1]
	for (int i=0; i<=n; i++) std::cin >> q[i]; // q[0], q[1], ... , q[n-1], q[n]
	
	double *cost_sum = new double[n+1];
	cost_sum[0] = q[0];
	for (int i=1; i<n+1; i++) cost_sum[i] = cost_sum[i-1] + p[i-1] + q[i]; 
	
	double** DP = new double*[n+1];
	for (int i=0; i<n+1; i++) DP[i] = new double[n];
	
	for (int j=0; j<n; j++) DP[j+1][j] = 0.0;
	
	for (int d=0; d<n; d++) {
		for (int i=0; i<n-d; i++) {
			if (d==0) DP[i][i] = q[i] + q[i+1];
			else {
				DP[i][i+d] = DBL_MAX;
				for (int j=0; j<=d; j++) {
					double left_cost_sum  = cost_sum[i+j] - cost_sum[i] + q[i];
					double right_cost_sum = cost_sum[i+d+1] - cost_sum[i+j+1] + q[i+j+1];
					DP[i][i+d] = min(DP[i][i+d], DP[i][i+j-1] + left_cost_sum + DP[i+j+1][i+d] + right_cost_sum);
				}
			}
			// std::cout << "DP[" << i << "][" << i+d << "] = " << DP[i][i+d] << std::endl;
		}
	}
	
	std::cout << std::fixed << DP[0][n-1] + 1 << std::endl;
	
	for (int i=0; i<n; i++) delete[] DP[i];
	delete[] DP;
	delete[] cost_sum;
	delete[] p;
	delete[] q;
	
	return 0;
}