直接上代码

#include

using namespace std;

const int N = 105;

int a[N], sum[N], dp1[N][N], dp2[N][N];

int main() {

int n; cin >> n;

memset(dp1, 0x3f, sizeof dp1);

memset(dp2, -0x3f, sizeof dp2);

for (int i = 1; i <= n; i++) {

    cin >> a[i];

    sum[i] = sum[i - 1] + a[i];

    dp1[i][i] = dp2[i][i] = 0;

}

for (int len = 2; len <= n; len++) {

    for (int l = 1; l + len - 1 <= n; l++) {

        int r = l + len - 1;

        for (int k = l; k < r; k++) {

            dp1[l][r] = min(dp1[l][r], dp1[l][k] + dp1[k + 1][r] + sum[r] - sum[l - 1]);

            dp2[l][r] = max(dp2[l][r], dp2[l][k] + dp2[k + 1][r] + sum[r] - sum[l - 1]);

         }

    }

}

cout << dp1[1][n] << endl << dp2[1][n];

return 0;
}