N – Slimes 解説 (Educational DP Contest / DP まとめコンテスト)
Contents
問題概要
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; }
ディスカッション
コメント一覧
まだ、コメントがありません