Educational DP Contest N - Slimes - 輪郭をなぞるだけのブログ

問題の概要

$N$ 匹のスライムが横一列に並んでいて、左から $i$ 番目のスライムの大きさは $a_{i}$ である。
隣り合う $2$ 匹のスライムを合体させて、 $1$ 匹のスライムにする。
このとき、 $2$ 匹のスライムの大きさを $x, y$ とすると、 $x+y$ のコストを支払う。
また、合体後の大きさは $x+y$ となる。
この操作を繰り返して、スライムを $1$ 匹にするまでのコストの最小値を求める。

制約

$2 \leq N \leq 400$
$1 \leq a_{i} \leq 10^{9}$

(考察 →) 実装

貪欲っぽく解けないかと思ったが、多分無理そう。(反例を考える気力がない…)

これも DP で解けるらしい。

$dp(left, right)$ を以下のように定義する。

$dp(left, right)$ := 半開区間 $[left, right)$ のスライムに対して合体処理を行った場合の、コストの総和の最小値

正直この設定も浮かばないのだが、世の人たち定義するのうますぎない？

それはさておき、次はどう遷移させるかである。
区間 $[left, right)$ を考えているとき、この区間を $pos$ で二つの区間に分割する。
分割された二つの区間は、 $[left, pos)$ と $[pos, right)$ となる。
この $pos$ は、開区間 $(left, right)$ 上を動く。
ある $pos$ で分割したときの図は以下のようになる。( $pos$ は $(right-left-2)$ 個ある。)
f:id:OutLine:20200112235652p:plain
区間が小さくなるまで、この分割操作を繰り返していき、その値を返していく。
分割統治法っぽい (?)

図は雑すぎるので、気が向いたら書き直すかも。
正直数列っぽく書いた方が見やすい気がするが、その気力がなかった…

$[left, pos)$ と $[pos, right)$ に分割したものを合体させるということは、区間 $[left, pos)$ で合体させたスライムと、区間 $[pos, right)$ で合体させたスライムとを合体させるということである。
区間 $[left, pos)$ でスライムを合体させるのに必要な最小コスト : $dp(left, pos)$
区間 $[pos, right)$ でスライムを合体させるのに必要な最小コスト : $dp(pos, right)$
であり、この二つのスライムを合体させるときにかかるコストは、
$S(i)$ := 配列 $a$ の左から $i$ 個の要素の総和とする (累積和を取る) と、 $\{ (S(pos) - S(left)) + (S(right) - S(pos)) \}$ となる。

一度訪問した区間をメモしておくと、計算量を削減できる。
計算量の見積りが分からない、多分 $O(N^{3})$ くらい。

ソースコードも載せておく。

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>
using namespace std;

#define chmin(x, y) x = min(x, y)

// 入力
int n;
vector<long long> a;
// dp[left][right] := 区間 [left,right) におけるコストの最小値
vector<vector<long long>> dp(405, vector<long long>(405, -1));
// スライムの大きさの累積和
long long S[405];

// メモ化再帰
long long memo_rec(int left, int right){
    if(dp[left][right] != -1)   return dp[left][right];
    if(right - left == 1)   return dp[left][right] = a[left];
    if(right - left < 1)    return 0;   // これは必要なわけではない

    long long res = numeric_limits<long long>::max();
    for(int pos = left + 1; pos < right; ++pos){
        long long tmp = 0;
        if(pos - left > 1)  tmp += memo_rec(left, pos) + S[pos] - S[left];
        else    tmp += memo_rec(left, pos);
        if(right - pos > 1) tmp += memo_rec(pos, right) + S[right] - S[pos];
        else    tmp += memo_rec(pos, right);
        chmin(res, tmp);
    }
    return dp[left][right] = res;
}

int main(){
    cin >> n;
    a.resize(n);
    for(int i = 0; i < n; ++i){
        cin >> a[i];
        S[i+1] = S[i] + a[i];
    }
    cout << memo_rec(0, n) << endl;
}