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