Go: package main

import (
	"bufio"
	"fmt"
	"log"
	"math"
	"os"
	"strconv"
	// "github.com/pkg/profile"
)

func mkTbl(n int, ds []float64) [][]float64 {
	tbl := make([][]float64, n+1)
	for i := range tbl {
		tbl[i] = make([]float64, n+1)
	}
	for i := 0; i <= n; i++ {
		tbl[i][i] = ds[i]
	}
	return tbl
}

func mkWeights(n int, ps, ds []float64) [][]float64 {
	tbl := mkTbl(n, ds)
	for i := 0; i < n; i++ {
		w := ds[i]
		for j := i + 1; j <= n; j++ {
			w += ps[j] + ds[j]
			tbl[i][j] = w
		}
	}
	return tbl
}

func minCost(i, j int, tbl [][]float64) float64 {
	m := math.MaxFloat64
	for k := i + 1; k <= j; k++ {
		m = math.Min(m, tbl[i][k-1]+tbl[k][j])
	}
	return m
}

func solve(n int, ps, ds []float64) float64 {
	costs := mkTbl(n, ds)
	weights := mkWeights(n, ps, ds)
	for l := 1; l <= n; l++ {
		for i := 0; i <= n-l; i++ {
			j := i + l
			costs[i][j] = weights[i][j] + minCost(i, j, costs)
		}
	}
	return costs[0][n]
}

func main() {
	// defer profile.Start(profile.ProfilePath(".")).Stop()

	w := bufio.NewWriter(os.Stdout)
	s := bufio.NewScanner(os.Stdin)
	s.Split(bufio.ScanWords)

	s.Scan()
	n, _ := strconv.Atoi(s.Text())
	ps := make([]float64, n+1)
	ds := make([]float64, n+1)

	for i := 1; i <= n; i++ {
		s.Scan()
		ps[i], _ = strconv.ParseFloat(s.Text(), 64)
	}

	for i := 0; i < n+1; i++ {
		s.Scan()
		ds[i], _ = strconv.ParseFloat(s.Text(), 64)
	}

	if s.Err() != nil {
		log.Fatal("scan error")
	}

	fmt.Fprintf(w, "%.4f\n", solve(n, ps, ds))
	_ = w.Flush()
}

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