AtCoder Educational DP Contest N問題解いてみた

今回の問題

問題文

$N$ 匹のスライムが横一列に並んでいます。
最初、左から $i$ 番目のスライムの大きさは $a_i$ です。

太郎君は、すべてのスライムを合体させて $1$ 匹のスライムにしようとしています。
スライムが $1$ 匹になるまで、太郎君は次の操作を繰り返し行います。

• 左右に隣り合う $2$ 匹のスライムを選び、それらを合体させて新しい $1$ 匹のスライムにする。
• 合体前の $2$ 匹のスライムの大きさを $x$ および $y$ とすると、合体後のスライムの大きさは $x+y$ となる。
• このとき、太郎君は $x+y$ のコストを支払う。

なお、合体の前後でスライムたちの位置関係は変わらない。
太郎君が支払うコストの総和の最小値を求めてください。

制約

• 入力はすべて整数である。
• $2 \leq N \leq 400$
• $1 \leq a_i \leq 10^9$

自分の回答

#include <bits/stdc++.h>
using namespace std;

const long long INF = 1e18;
long long dp[405][405];
long long A[405];
long long S[405];

int main() {
    int N;
    cin >> N;
    for(int i = 1; i <= N; i++) {
        cin >> A[i];
    }
    S[0] = 0;
    for(int i = 1; i <= N; i++) {
        S[i] = S[i-1] + A[i];
    }
    
    for(int i = 1; i <= N; i++) {
        for(int j = 1; j <= N; j++) {
            if (i == j) dp[i][j] = 0;
            else dp[i][j] = INF;
        }
    }
    
    for(int len = 2; len <= N; len++) {
        for(int i = 1; i <= N - len + 1; i++) {
            int j = i + len - 1; 
            long long sum_range = S[j] - S[i-1];
            
            for(int k = i; k < j; k++) {
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + sum_range);
            }
        }
    }
    
    cout << dp[1][N] << endl;
    
    return 0;
}

解説

区間dpでとく。ある区間lrで組み合わせるときのコストの最小値をdpテーブルにメモしておく。これにより、
dp[i][j] = min(dp[i][k] + dp[k+1][j]) + (区間 [i, j] のスライムの大きさの総和)となる。
これは最後の一個になる前の状態を考えていくと思いつくのかなと思う。区間dp頭良すぎる。