C++で長さa、b、cのセグメントの最大数を求める方法

正の整数Nが与えられたとき、そのNを長さa、b、cの線分に分割して、最大で何個のセグメントを作成できるかを求めるのが本課題です。

具体例を使って、何をすべきか見ていきましょう。

入力 − N=8, a=3, b=1, c=2

出力 − 8

説明 − Nは長さbのセグメント8個に分割でき、これが作成可能なセグメントの最大数となります。

入力 − N=13, a=2, b=7, c=3

出力 − 6

プログラムで使用するアプローチ

この問題は動的計画法（DP）を用いて効率的に解くことができます。配列MaxSeg[i]には、長さiを作成するために必要なセグメントの最大数を格納します。具体的な手順は以下の通りです。

• MaxSegment()関数内で、int型の配列MaxSeg[N+1]を宣言し、すべての要素を-1で初期化します。-1は「その長さを作成できない」ことを意味します。

• 0番目のインデックスには0を設定します。長さ0にはセグメントが存在しないためです。

• i=0からi<Nまでループし、MaxSeg[i] != -1であるかどうかを確認します。

• 上記の条件を満たす場合、さらにi + a <= Nであるかをチェックし、条件を満たしていればMaxSeg[i + a] = max(MaxSeg[i] + 1, MaxSeg[i + a])を設定します。

• 長さbとcについても同様の処理を繰り返します。

• ループ終了後、MaxSeg[N]を返します。

例

#include <bits/stdc++.h>
using namespace std;
int MaxSegment(int N, int a,int b, int c){
   /* 各インデックスが持つセグメントの最大数を格納 */
   int MaxSeg[N + 1];
   // 初期化
   memset(MaxSeg, -1, sizeof(MaxSeg));
   // 0番目のインデックスはセグメント数0
   MaxSeg[0] = 0;
   // nまでの各セグメントを走査
   for (int i = 0; i < N; i++){
      if (MaxSeg[i] != -1){
         if(i + a <= N ){
            MaxSeg[i + a] = max(MaxSeg[i] + 1, MaxSeg[i + a]);
         }
         if(i + b <= N ){
            MaxSeg[i + b] = max(MaxSeg[i] + 1, MaxSeg[i + b]);
         }
         if(i + c <= N ){
            MaxSeg[i + c] = max(MaxSeg[i] + 1, MaxSeg[i + c]);
         }
      }
   }
   return MaxSeg[N];
}
int main(){
   int N = 13, a = 2, b = 7, c = 3;
   cout << MaxSegment(N, a, b, c);
   return 0;
}

出力

上記のコードを実行すると、以下の出力が得られます。

6