1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 const LL INF = 100000000000000000LL; 5 LL dp[1010][1010], s[1010][1010]; 6 LL sum[1010]; 7 int main() { 8     LL ans = 0; 9     int n; scanf("%d", &n);10     for(int i = 1; i <= n; i++) scanf("%lld", &dp[i][i]), sum[i] = sum[i-1] + dp[i][i], dp[i][i] = 0, s[i][i] = i;11     for(int len = 1; len < n; len++) {12         for(int l = 1; l + len <= n; l++) {13             int r = l + len;14             dp[l][r] = INF;15             for(int k = s[l][r-1]; k <= s[l+1][r]; k++) {16                 LL now = dp[l][k] + dp[k+1][r] + sum[r] - sum[l - 1];17                 if(dp[l][r] > now) dp[l][r] = now, s[l][r] = k;18             }19         }20     }21     printf("%lld\n", dp[1][n]);22     return 0;23 }