区間分割をしていく DP として、一番最初に解くべき問題を意図して作った！！　けんちょん本の 3 例題 (ナップサック問題、編集距離、これ) の 1 つでもある。

問題へのリンク

問題概要

$N$ 個の要素が一列に並んでいる。これら $N$ 個の要素に対して、区間 $\lbrack i, j)$ のコストは $c_{i, j}$ で与えられる。

これら $N$ 個の要素を何個かの区間に分割していく。区間分割のコストは、下図のように、各区間のコストの総和で与えられる。

区間分割の仕方を最適化したときの、最小コストを求めよ。

制約

$1 \le N \le 1000$
$0 \le c_{i, j} \le 100$

解法

次の DP を立てる。

dp[i] ← 最初の $i$ 個の要素 $0, 1, \dots, i-1$ のみを考えたときの、区間分割の仕方を最適化したときの最小コスト (要素 $i-1, i$ 間に仕切りを入れるものとする)

このとき、dp[i] の値を求めるために、最後の仕切り (要素 $i-1, i$ の間の仕切りを除いて、その手前の仕切り) の位置がどこなのかで場合分して考えることにする。それが要素 $j-1, j$ 間の仕切りである場合、下図のように

最初の $j$ 個の要素 $0, 1, \dots, j-1$ を最適分割した上で
最後の区間 $\lbrack j, i)$ のスコアを足す

という場合が最適となる。よって、DP の更新式は

dp[i] = min(dp[i], dp[j] + c[j][i])

と表せる。

この更新式を実装することで AC できる。計算量は $O(N^{2})$ となる。

コード

#include <bits/stdc++.h>
using namespace std;
const int INF = 1<<29;

int main() {
    int N;
    cin >> N;
    vector<vector<int>> c(N+1, vector<int>(N+1));
    for (int i = 0; i < N+1; ++i) for (int j = 0; j < N+1; ++j) cin >> c[i][j];
    
    // DP
    vector<int> dp(N+1, INF);
    dp[0] = 0;  // 初期条件
    for (int i = 1; i <= N; ++i) {
        for (int j = 0; j < i; ++j) {
            dp[i] = min(dp[i], dp[j] + c[j][i]);
        }
    }
    cout << dp[N] << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

PAST 本上級〜エキスパート編 A - 区間分割の仕方を最適化する問題

問題概要

制約

解法

コード