Slimes [Educational DP Contest / DP まとめコンテスト N]

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

前提知識

• 区間DP

解説

https://atcoder.jp/contests/dp/submissions/3955596

区間DPをする。
dp(L, R) := [L,R]の区間のスライムを1つにするためのコストの総和の最小値
自分は区間DPはメモ化再帰で実装するのが好きなので、そうしている。
ループで実装する場合は、区間が小さい方から順番に計算するように気をつけよう。
　
[L,R]の区間のスライムを1つにする一手前の状態を考えると、[L,R]が2つに別れていることが分かる。
なので、分ける境界を全探索して、コストの最小値を求めていく。
累積和で区間和を高速に求められるようにしておかないとTLEする。

int N; ll A[401];
//---------------------------------------------------------------------------------------------------
ll B[404];
void init() {
    B[0] = A[0];
    rep(i, 1, N) B[i] = B[i - 1] + A[i];
}
ll get(int L, int R) {
    ll res = B[R];
    if (L) res -= B[L - 1];
    return res;
}
//---------------------------------------------------------------------------------------------------
ll memo[404][404];
int vis[404][404];
ll dp(int L, int R) {
    if (L == R) return 0;
    if (vis[L][R]) return memo[L][R];
    vis[L][R] = 1;
 
    ll res = infl;
    rep(c, L, R) chmin(res, dp(L, c) + dp(c + 1, R) + get(L, R));
    return memo[L][R] = res;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
    init();
    cout << dp(0, N - 1) << endl;
}