C ++での長さa、b、cのセグメントの最大数

与えられた正の整数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

以下のプログラムで使用されるアプローチは次のとおりです

• 関数MaxSegment（）で、int型の配列MaxSeg [N +1]を宣言し、値-1で初期化します。

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

• i =0からi

• 上記のifステートメントの中に別のステートメントを入れますif（i + a <=N）and putMaxSeg [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){
   /* It will store the maximum number of segments each index can have*/
   int MaxSeg[N + 1];
   // initialization
   memset(MaxSeg, -1, sizeof(MaxSeg));
   // 0th index will have 0 segments
   MaxSeg[0] = 0;
   // traversing for every segments till 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