N – Slimes 解説 (Educational DP Contest / DP まとめコンテスト)

2020年3月10日AtCoderDP,競プロ,区間DP,区間の除去・圧縮・合体

問題へのリンク

問題概要

N 個の数列 \({a_1, a_2, a_3, \cdots, a_N\}\) があり、以下の操作を数列の要素数が 1 になるまで繰り返す。

  • 隣り合う2つ \(a, b\) を選んで取り除き、かわりに a+b を置く。この時コスト a+b を払う

支払うコストの合計の最小値はいくつになるか？

制約

  • \(2 \leq N \leq 400\)
  • \(1 \leq a_i \leq 10^9\)

考え方

「区間の除去・圧縮・合体」などがあるときは、区間DP を用いると上手くいくことがあります。

典型的な区間DPの形に合わせると、以下のようなDPになります。

\(dp[ l ][ r ]\) := 区間 [ l, r ) について、1つになるまで操作を行った時の支払うコストの合計の最小値

更新は以下のようにすれば良いです。

  • dp[ l ][ r ] = min( dp[ l ][ i ] + dp[ i ][ r ] +「 区間 [ l, r )の合計値」 )

区間を2つに分けて、それぞれの区間を1つにまとめてから、できた2つを最終的に1つにまとめています。

この時支払うコストはどのようなまとめ方をしても、 「区間 [ l, r )の合計値」に等しいです。

区間の合計値を累積和などで別に用意しておくか、dp の配列にまとめて保存しておくと良いでしょう。

C++ での実装例

区間DPは for 文で実装するのが難しいので、メモ化再帰で実装するのがおすすめです。

区間の合計値は配列にまとめて保持しています。

#include <bits/stdc++.h>
#define ALL(obj) begin(obj), end(obj)
using namespace std;
template <class T>
bool chmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}

using ll = long long;
using P = pair<ll, ll>;
const ll INF = 1e18;

int N;
vector<ll> a;
vector<vector<P>> dp;  // first: コストの合計の最小値、second: 1つにまとめた時の値

P rec(int l = 0, int r = N) {  // メモ化再帰
    if (r - l == 1) return make_pair(0, a[l]);
    P &ret = dp[l][r];
    if (ret.first != INF) return ret;

    for (int i = l + 1; i < r; i++) {
        P L = rec(l, i);
        P R = rec(i, r);
        ll sum = L.second + R.second;
        ll cost = L.first + R.first + sum;
        chmin(ret, make_pair(cost, sum));
    }

    return ret;
}

int main() {
    cin >> N;
    a.resize(N);
    for (int i = 0; i < N; i++) {
        cin >> a.at(i);
    }

    dp.assign(N + 2, vector<P>(N + 2, make_pair(INF, 0)));  // 初期化

    cout << rec().first << endl;

    return 0;
}

AtCoderDP,競プロ,区間DP,区間の除去・圧縮・合体