প্রদত্ত টাস্ক হল a, b এবং c দৈর্ঘ্যের সর্বাধিক সংখ্যক লাইন সেগমেন্ট খুঁজে বের করা যা প্রদত্ত ধনাত্মক পূর্ণসংখ্যা N থেকে গঠিত হতে পারে।
আসুন এখন বুঝতে পারি −
একটি উদাহরণ ব্যবহার করে আমাদের কী করতে হবেইনপুট − 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-এর সমান রাখুন কারণ এতে কোনো সেগমেন্ট থাকবে না।
-
i=0 থেকে i
-
উপরের if স্টেটমেন্টের ভিতরে আরেকটি স্টেটমেন্ট লিখুন if(i + a <=N) এবং 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
