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++: #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;
}