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++: #include<bits/stdc++.h>
#define ll long long
#define rep(i, n) for(int i=0;i<(n);++i)
#define per(i, n) for(int i=(n)-1;i>=0;--i)
#define repa(i, n) for(int i=1;i<(n);++i)
#define foreach(i, n) for(auto &i:(n))
#define pii pair<int, int>
#define pll pair<long long, long long>
#define all(x) (x).begin(), (x).end()
#define bit(x) (1ll << (x))
const ll MOD = (ll)1e9+7;
const int INF = (ll)1e9+7;
const ll INFLL = (ll)1e18;
using namespace std;
template<class t>
using vvector = vector<vector<t>>;
template<class t>
using vvvector = vector<vector<vector<t>>>;
template<class t>
using priority_queuer = priority_queue<t, vector<t>, greater<t>>;
template<class t, class u> bool chmax(t &a, u b){if(a<b){a=b;return true;}return false;}
template<class t, class u> bool chmin(t &a, u b){if(a>b){a=b;return true;}return false;}

ll modpow(ll x, ll b){
	ll res = 1;
	while(b){
		if(b&1)res = res * x % MOD;
		x = x * x % MOD;
		b>>=1;
	}
	return res;
}

ll modinv(ll x){
	return modpow(x, MOD-2);
}

int n;
vector<double> p;
vector<double> sump;
vector<double> q;
vector<double> sumq;
vvector<double> dp;

double func(int l, int r){
	if(r<l)return 0;
	if(l==r){
		return p[l] + 2 * q[l-1] + 2 * q[l];
	}
	if(dp[l][r] >= 0)return dp[l][r];
	double res = INFLL;
	chmin(res, q[l-1]*2+p[l]+func(l+1, r)+sump[r]-sump[l]+sumq[r]-sumq[l-1]);
	chmin(res, q[r]*2+p[r]+func(l, r-1)+sump[r-1]-sump[l-1]+sumq[r-1]-sumq[l-2]);
	for(int mid=l+1;mid<r;++mid){
		double midsum = p[mid];
		double leftsum = func(l, mid-1) + sump[mid-1] - sump[l-1] + sumq[mid-1] - sumq[l-2];
		double rightsum = func(mid+1, r) + sump[r] - sump[mid] + sumq[r] - sumq[mid-1];
		chmin(res, midsum+leftsum+rightsum);
	}
	return dp[l][r] = res;
}

int main(){
	cin >> n;
	p.resize(n+2);
	q.resize(n+3);
	sump.resize(n+3, 0);
	sumq.resize(n+4, 0);
	for(int i=2;i<n+2;++i){
		cin >> p[i];
		sump[i] = sump[i-1] + p[i];
	}
	for(int i=1;i<n+2;++i){
		cin >> q[i];
		sumq[i] = sumq[i-1] + q[i];
	}
	dp.resize(n+2, vector<double>(n+2, -1));
	printf("%.8lf\n", func(2, n+1));
	return 0;
}

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

int main()
{
	int n;
	scanf("%d", &n);

	using vd = std::vector<double>;
	using vvd = std::vector<vd>;
	vd percentage(2 * n + 2);
	for (int i{2}; i < 2 * n + 2; i += 2)
		scanf("%lf", &percentage[i]);
	for (int i{1}; i < 2 * n + 2; i += 2)
		scanf("%lf", &percentage[i]);

	vvd dp(n + 1, vd(n + 1, 9));
	for (int i{}; i <= n; i++)
		dp[i][i] = 0;

	for (int i{1}; i < 2 * n + 2; i++)
		percentage[i] += percentage[i - 1];

	for (int width{1}; width <= n; width++)
		for (int left{}; left + width <= n; left++)
		{
			int right{left + width};
			for (int root{right}; root > left; root--)
				dp[left][right] = std::min(dp[left][right],
				dp[left][root - 1] + percentage[2 * root - 1] - percentage[2 * left]
				+ dp[root][right] + percentage[2 * right + 1] - percentage[2 * root]
				);
		}

	std::cout << std::fixed << std::setprecision(6) << dp[0][n] + 1 << std::endl;

	return 0;
}