数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++中长度为a、b和c的线段最大数量
给定任务是从给定的正整数N中找到可以形成的长度为a、b和c的线段的最大数量。
让我们用一个例子来理解我们必须做什么：
输入 - N=8，a=3，b=1，c=2
输出 - 8
解释 - N可以分成8个长度为b的线段，这是可以形成的最大线段数。
输入 - N=13，a=2，b=7，c=3
输出 - 6
下面程序中使用的算法如下：
在MaxSegment()函数中，声明一个类型为int的数组MaxSeg[N+1]，并将其初始化为-1。
将第零个索引设置为0，因为它没有线段。
循环从i=0到i
在上面的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];
// 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
更新于：2020年8月17日
191 次浏览
广告