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。

• 由于第零个索引没有分段，因此将其置零。

• 从i = 0循环直到i <N，然后检查（MaxSeg [i]！= -1）。

• 在上面的if语句中放入另一个语句if（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){
   /* It will store the maximum number of segments each index can have*/
   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