C++で長さp、q、rのセグメント数を最大化する方法

問題文

長さ L の棒が与えられます。この棒を、長さ p、q、r のセグメントの合計数が最大になるように切断することが課題です。セグメントの長さとして許されるのは p、q、r のみです。

例えば、l = 15、p = 2、q = 3、r = 5 の場合、次のように7個のセグメントを作ることができます。

{2, 2, 2, 2, 2, 2, 3}

アルゴリズム

この問題は動的計画法(DP)を使って効率的に解くことができます。各位置において「そこまで到達できるか」「到達できるなら最大何回の切断が可能か」を順に求めていくのがポイントです。

1. dp[] 配列を初期化します。まだ到達できない位置を表すため -1 で埋め、起点となる dp[0] = 0 とします。
2. 棒の長さ l まで反復処理を行います。各位置 i について、可能であれば長さ p、q、r の切断を実行します。
3. 可能なすべての切断に対して、ans[i+p] = max(ans[i+p], 1 + ans[i])、ans[i+q] = max(ans[i+q], 1 + ans[i])、ans[i+r] = max(ans[i+r], 1 + ans[i]) を更新します。
4. i 番目の位置への到達が不可能な場合、その値は -1 のままスキップされます。最終的に ans[l] が最大の切断回数を返します。

計算量は O(L) であり、各位置を一度だけ走査すればよいため非常に高速です。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;
int getMaximumSegments(int l, int p, int q, int r){
    int dp[l + 1];
    memset(dp, -1, sizeof(dp));
    dp[0] = 0;
    for (int i = 0; i <= l; ++i) {
        if (dp[i] == -1) {
            continue;
        }
        if (i + p <= l) {
            dp[i + p] = max(dp[i + p], dp[i] + 1);
        }
        if (i + q <= l) {
            dp[i + q] = max(dp[i + q], dp[i] + 1);
        }
        if (i + r <= l) {
            dp[i + r] = max(dp[i + r], dp[i] + 1);
        }
    }
    return dp[l];
}
int main(){
    int l = 15, p = 2, q = 3, r = 5;
    cout << "Number of segments = " << getMaximumSegments(l, p, q, r) << endl;
    return 0;
}

出力

上記のプログラムをコンパイルして実行すると、次の出力が得られます。

Number of segments = 7

この結果から、長さ15の棒を長さ2、3、5のセグメントに分割したとき、最大7個のセグメント(2×6個と3×1個)に切り分けられることが分かります。