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++:     /*
　　　∫ ∫ ∫
　　　ノヽ
　　（＿　 ）
　（＿　　　 ）
（＿＿＿＿＿＿ ）
　ヽ(´･ω･)ﾉ　
　　 |　 /
　　 UU
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
using P = pair<ll, ll>;
const int MOD = (int)1e9 + 7;
const ll INF = 1LL << 60;
const int inf = 1<<30;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
#define REP(i, n) for (int i = 0; i < (n); i++)
#define FOR(i,s,n) for (int i = s; i < (n); i++)
#define ALL(obj) (obj).begin(), (obj).end() //コンテナじゃないと使えない!!
#define debug(x) cerr << #x << ": " << x << "\n";
#define mp make_pair
template <typename T>
ostream& operator<<(ostream& os, vector<T> &V){
    int N = V.size();
    REP(i,N){
        os << V[i];
        if (i!=N-1) os << " ";

    }
    os << "\n";
    return os;
}

ld solve(vector<ld>& P, int N){
    /*
        区間[s,t]をiで分割する
        　　　i
        　子    子
        ・・・　・・・
        にする(今回はダミーは関節点に来ないことに注意)
    
        すると、dp[s][t] = min(dp[s][i-1] + dp[i+1][t]) + (s~tのコストの和)で表せる  (s<i<t かつ　実際の(ダミーでない)ノード)
    */
   vector<vector<ld>> dp(N,vector<ld>(N,1<<30)); 
    for(int i=0;i<N;i++) dp[i][i] = P[i]; 
    
    vector<ld> cumsum(N+1,0);
    REP(i,N) {cumsum[i+1]=cumsum[i]+P[i];}  //累積和(s~tのコストの和をO(1)で使うために)
    for(int i=2 ;i<N;i+=2){ 
        for(int left=1;left < N-i;left+=2){ // ダミー,...,ダミーを単位としてやる
            int right = left + i; //区間右端(閉)
            for(int mid = left+1; mid<right; mid+=2){ //ダミーは関節点に来ない
                chmin(dp[left][right], dp[left][mid-1] + dp[mid+1][right]); //上記の分割
            }
            dp[left][right] += cumsum[right+1]-cumsum[left];
        }
    }
    ld res = dp[1][N-1]; //1-indexに注意
    return res;
}
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    int L = 2*(N+1);  
    vector<ld> P(L,0);//1-index   DVDVDVDVDVDVDVDVD (D:ダミー,V:実際の)
    REP(i,N) cin >> P[2*(i+1)];
    REP(i,N+1) cin >> P[2*i+1];

    ld ans=solve(P,L);
    cout << fixed<<setprecision(10)<<ans<<endl;
}

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

struct Precision{
  Precision(){
    cout<<fixed<<setprecision(12);
  }
}precision_beet;


template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

//INSERT ABOVE HERE
signed main(){
  Int n;
  cin>>n;
  vector<double> p(n),q(n+1);
  for(Int i=0;i<n;i++) cin>>p[i];
  for(Int i=0;i<=n;i++) cin>>q[i];

  static double dp[555][555];
  for(Int i=0;i<555;i++)
    for(Int j=0;j<555;j++) dp[i][j]=-1;

  function<double(Int, Int)> dfs=
    [&](Int l,Int r)->double{
      double &res=dp[l][r];
      if(res>=0) return res;
      res=1e18;
      
      double s=0;
      for(Int i=l;i<r;i++) s+=p[i];
      for(Int i=l;i<=r;i++) s+=q[i];

      for(Int i=l;i<r;i++){
	double tmp=s;
	tmp+=i==l?q[l]:dfs(l,i);
	tmp+=i+1==r?q[r]:dfs(i+1,r);
	chmin(res,tmp);
      }
      
      return res;
    };
  
  cout<<dfs(0,n)<<endl;  
  return 0;
}

C++: #define _USE_MATH_DEFINES
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <clocale>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define FOR(i, s, n) for(int i = (s), i##_len=(n); i < i##_len; ++i)
#define FORS(i, s, n) for(int i = (s), i##_len=(n); i <= i##_len; ++i)
#define VFOR(i, s, n) for(int i = (s); i < (n); ++i)
#define VFORS(i, s, n) for(int i = (s); i <= (n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define REPS(i, n) FORS(i, 0, n)
#define VREP(i, n) VFOR(i, 0, n)
#define VREPS(i, n) VFORS(i, 0, n)
#define RFOR(i, s, n) for(int i = (s), i##_len=(n); i >= i##_len; --i)
#define RFORS(i, s, n) for(int i = (s), i##_len=(n); i > i##_len; --i)
#define RREP(i, n) RFOR(i, n, 0)
#define RREPS(i, n) RFORS(i, n, 0)
#define ALL(v) (v).begin(), (v).end()
#define SORT(v) sort(ALL(v))
#define RSORT(v) sort(ALL(v), greater<decltype(v[0])>())
#define SZ(x) ((int)(x).size())
#define PB push_back
#define MP make_pair
#define MT make_tuple
#define BIT(n) (1LL<<(n))
#define UNIQUE(v) v.erase(unique(ALL(v)), v.end())

using ll = long long;
using Pi_i = pair<int, int>;
using VB = vector<bool>;
using VC = vector<char>;
using VD = vector<double>;
using VI = vector<int>;
using VLL = vector<ll>;
using VS = vector<string>;
using VSH = vector<short>;

const int MOD = 1000000007;
const int INF = 1000000000;
const int NIL = -1;

template<class T>
bool chmax(T &a, const T &b){
    if(a < b){
        a = b; return true;
    }
    return false;
}
template<class T>
bool chmin(T &a, const T &b){
    if(b < a){
        a = b; return true;
    }
    return false;
}



int main(){
    int n; cin >> n;
    VD p(n+1), q(n+1), sump(n+1), sumq(n+2);
    FORS(i, 1, n){
        cin >> p[i]; sump[i] = sump[i-1] + p[i];
    }
    REPS(i, n){
        cin >> q[i]; sumq[i+1] = sumq[i] + q[i];//attention
    }
    vector<VD> dp(n+1, VD(n+1, 0.0));
    FORS(i, 1, n) dp[i][i] = p[i] + 2*q[i-1] + 2*q[i];

    FORS(l, 2, n){
        FORS(i, 1, n - l + 1){
            int j = i + l - 1;
            dp[i][j] = INF;
            FORS(k, i, j){
                if(k == i) chmin(dp[i][j],
                                 p[i] + 2*q[i-1] + dp[i+1][j] + sump[j] - sump[i] + sumq[j+1] - sumq[i]);
                else if(k == j) chmin(dp[i][j],
                                 p[j] + 2*q[j] + dp[i][j-1] + sump[j-1] - sump[i-1] + sumq[j] - sumq[i-1]);
                else chmin(dp[i][j],
                     dp[i][k-1] + dp[k+1][j] + sump[j] - sump[i-1] + sumq[j+1] - sumq[i-1]);
            }
        }
    }
    cout << fixed << setprecision(10) << dp[1][n] << "\n";
    return 0;
}