Số lượng phân đoạn có độ dài a, b và c tối đa trong C ++

Nhiệm vụ được giao là tìm số đoạn thẳng có độ dài a, b và c lớn nhất có thể được tạo thành từ số nguyên dương N cho trước.

Bây giờ chúng ta hãy hiểu những gì chúng ta phải làm bằng cách sử dụng một ví dụ -

Đầu vào - N =8, a =3, b =1, c =2

Đầu ra - 8

Giải thích - N có thể được chia thành 8 đoạn trong đó b là số đoạn tối đa có thể được tạo ra.

Đầu vào - N =13, a =2, b =7, c =3

Đầu ra - 6

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau

• Trong hàm MaxSegment () khai báo một mảng MaxSeg [N +1] kiểu int và khởi tạo nó với giá trị -1.

• Đặt chỉ mục thứ 0 bằng 0 vì nó sẽ không có phân đoạn.

• Lặp lại từ i =0 đến i

• Bên trong câu lệnh if ở trên đặt một câu lệnh khác if (i + a <=N) và putMaxSeg [i + a] =max (MaxSeg [i] + 1, MaxSeg [i + a]);

• Lặp lại bước trên cho cả b và c.

• Bên ngoài vòng lặp, trả về MaxSeg [N].

Ví dụ

#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;
}

Đầu ra

Nếu chúng ta chạy đoạn mã trên, chúng ta sẽ nhận được kết quả sau -

6