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++: #define _CRT_SECURE_NO_WARNINGS

#include<iostream>
#include<functional>
#include<algorithm>
#include<stack>
#include<queue>
#include<iomanip>
#include<set>
#include<map>
#include<utility>
#include<string>
#include<vector>

using namespace std;

#define LL long long

int n;
double cost[1002],sum[1005]={},memo[1005][1005];

double exp(int l,int r){
	if(memo[l][r]!=-1.0)return memo[l][r];
	double ret=1000000000.0;
	if(l==r)ret=cost[l];
	else{
		for(int k=l+1;k<r;k+=2)
			ret=min(ret,exp(l,k-1)+exp(k+1,r)+sum[r]-(l==0?0.0:sum[l-1]));
	}
	return memo[l][r]=ret;
}


int main() {
	cin>>n;
	for(int i=0;i<=2*n+2;i++)for(int j=0;j<=2*n+2;j++)memo[i][j]=-1.0;
	for(int i=1;i<=n;i++)cin>>cost[2*i];
	for(int i=0;i<=n;i++)cin>>cost[2*i+1];
	for(int i=1;i<=2*n+2;i++)sum[i]=cost[i]+sum[i-1];
	cout<<fixed<<exp(1,2*n+1)<<endl;
	return 0;
}

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