Solution for https://atcoder.jp/contests/dp/tasks/dp_n

sol.cc

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define FOR(i, j, k, in) for (ll i = j; i < k; i += in)
#define RFOR(i, j, k, in) for (ll i = j; i >= k; i -= in)
#define REP(i, j) FOR(i, 0, j, 1)
#define RREP(i, j) RFOR(i, j, 0, 1)

ll dp[400][400], val[400][400];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector<ll> ais(n);
    REP(i, n)
    cin >> ais[i];
    ll infinity = 400000000001ll;

    memset(dp, infinity, sizeof(dp[0][0]) * 400 * 400);
    memset(val, 0, sizeof(dp[0][0]) * 400 * 400);

    REP(i, n)
    dp[i][i] = 0;

    REP(i, n) {
        REP(j, n) {
            if (i == j)
                val[i][j] = ais[i];
            else
                val[i][j] = val[i][j - 1] + ais[j];
        }
    }

    FOR(s, 1, n, 1) {
        REP(i, n) {
            if (i + s >= n) break;
            int b = i, t = i + s;
            FOR(j, b, t, 1) {
                dp[b][t] = min(dp[b][t], dp[b][j] + dp[j + 1][t] + val[b][j] + val[j + 1][t]);
            }
        }
    }

    cout << dp[0][n - 1] << endl;

    return 0;
}