o60_may08_guesscost

#include <bits/stdc++.h>

using namespace std;
const int N = 300 + 10;
const int INF = 1e9;
int ar[N], dp[N][N];

int f(int i, int j){
    if(i > j) return 0;
    else if(i == j) return dp[i][j] = ar[i];
    else if(j == i + 1) return dp[i][j] = ar[i] + ar[j];
    if(dp[i][j] != INF) return dp[i][j];
    for(int k=i+1;k<=j-1;k++)
        dp[i][j] = min(dp[i][j], ar[k] + max(f(i, k-1), f(k+1, j)));
    return dp[i][j];
}

int main(){

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

    for(int i=1;i<=n;i++) scanf("%d", &ar[i]);

    for(int i=1;i<=n;i++)
        dp[i][i] = ar[i];

    for(int i=n;i>=1;i--){
        for(int j=i+1;j<=n;j++){
            dp[i][j] = INF;
            for(int k=i;k<=j;k++)
                dp[i][j] = min(dp[i][j], ar[k] + max(dp[i][k-1], dp[k+1][j]));
        }
    }

    printf("%d", dp[1][n]);

    return 0;
}