C++で整数配列を1つの値にマージする最小コストを求めるプログラム

n個の正の整数を含む配列 arr と、整数 j が与えられます。私たちの課題は、j個の数値を選んで足し合わせることで、それらを1つの数値にマージすることです。マージのコストは、選択したj個の数値の合計に等しくなります。このマージ操作全体にかかる最小のコストを求めるのが目標です。

例えば、入力が arr = [2, 5, 6, 2, 3, 1, 3]、j = 4 の場合、出力は 31 になります。

まず、2, 3, 1, 3 をマージするコストは 2 + 3 + 1 + 3 = 9 です。このマージ操作の後、配列は [2, 5, 6, 9] となります。続く2回目のマージ操作のコストは 2 + 5 + 6 + 9 = 22 です。したがって、マージ操作の合計コストは 22 + 9 = 31 となり、これが最小のマージコストとなります。

解決アプローチ

この問題は、区間DP(動的計画法)を用いて効率的に解くことができます。まず、(n - 1) が (j - 1) で割り切れない場合、すべての要素を最終的に1つの値にまとめることができないため、-1 を返します。その上で、以下の手順に従います。

• n := 配列 arr のサイズとする
• (n - 1) mod (j - 1) が 0 でない場合は、-1 を返す
• サイズ n + 1 の配列 temp を定義し、後ろからの累積和を計算する
• i := n - 1 から i >= 0 まで、i を 1 ずつ減らしながら繰り返す:
  • temp[i] := arr[i] + temp[i + 1]
• n × n の2次元配列 dynArr を定義する
• k := j から k <= n まで、k を 1 ずつ増やしながら繰り返す:
• le := 0、rg := k - 1 から rg < n の間、le と rg を 1 ずつ増やしながら繰り返す:
  • dynArr[le, rg] := 無限大
  • i := le から i < rg まで、i を (j - 1) ずつ増やしながら繰り返す:
    • dynArr[le, rg] := min(dynArr[le, rg], dynArr[le, i] + dynArr[i + 1, rg])
  • (rg - le) mod (j - 1) が 0 と等しい場合:
    • dynArr[le, rg] := dynArr[le, rg] + temp[le] - temp[rg + 1]
• dynArr[0, n - 1] を返す

実装例

理解を深めるために、以下のC++による実装を見てみましょう。

#include<bits/stdc++.h>
using namespace std;
int solve(vector<int>& arr, int j) {
    int n = arr.size();
    if ((n - 1) % (j - 1) != 0) return -1;

    vector<int> temp(n + 1);
    for (int i = n - 1; i >= 0; i--) {
        temp[i] = arr[i] + temp[i + 1];
    }
    vector<vector<int>> dynArr(n, vector<int>(n));
    for (int k = j; k <= n; k++) {
        for (int le = 0, rg = k - 1; rg < n; le++, rg++) {
            dynArr[le][rg] = INT_MAX;
            for (int i = le; i < rg; i += j - 1) {
                dynArr[le][rg] = min(dynArr[le][rg], dynArr[le][i] + dynArr[i + 1][rg]);
            }
            if ((rg - le) % (j - 1) == 0) {
                dynArr[le][rg] += temp[le] - temp[rg + 1];
            }
        }
    }
    return dynArr[0][n - 1];
}

int main() {
    vector<int> arr = {2, 5, 6, 2, 3, 1, 3};
    cout << solve(arr, 4) << endl;
    return 0;
}

入力

{2, 5, 6, 2, 3, 1, 3}, 4

出力

31