1 #include <bits/stdc++.h> 2 using namespace std; 3 const int maxn = 205; 4 const int inf = 0x3f3f3f3f; 5 int cost1[maxn][maxn], cost2[maxn][maxn]; //当前合并的代价 6 int dp1[maxn][maxn], dp2[maxn][maxn]; 7 int main() { 8 int n; cin >> n; 9 for (int i = 1; i <= n; i++) { 10 cin >> cost1[i][i]; 11 cost2[i][i] = cost1[i][i]; 12 } 13 for (int i = 1; i <= n; i++) { 14 cost1[n+i][n+i] = cost1[i][i]; 15 cost2[n+i][n+i] = cost2[i][i]; 16 } 17 n <<= 1; 18 for (int i = 2; i <= n/2; i++) { 19 for (int j = 0; j <= n-i; j++) { 20 int x = i+j, y = j+1; 21 for (int k = 1; k < i; k++) { 22 cost1[x][y] = cost1[x-k][y] + cost1[x][y+i-k]; 23 cost2[x][y] = cost2[x-k][y] + cost2[x][y+i-k]; 24 if (dp1[x][y]) dp1[x][y] = min(dp1[x][y],cost1[x][y]+dp1[x-k][y]+dp1[x][y+i-k]); 25 else dp1[x][y] = cost1[x][y]+dp1[x-k][y]+dp1[x][y+i-k]; 26 if (dp2[x][y]) dp2[x][y] = max(dp2[x][y],cost2[x][y]+dp2[x-k][y]+dp2[x][y+i-k]); 27 else dp2[x][y] = cost2[x][y]+dp2[x-k][y]+dp2[x][y+i-k]; 28 } 29 } 30 } 31 int mi = inf, mx = 0; 32 n >>= 1; 33 for(int j = 0; j <= n; j++) { 34 mi = min(mi,dp1[n+j][j+1]); 35 } 36 for(int j = 0; j <= n; j++) { 37 mx = max(mx,dp2[n+j][j+1]); 38 } 39 cout << mi << endl << mx << endl; 40 }