সি++ কোড হাউস মেকিং করে সর্বোচ্চ লাভ পেতে

ধরুন আমাদের দুটি সংখ্যা n এবং h, এবং m ট্রিপলেট T এর আরেকটি অ্যারে আছে, যেখানে T[i] =(li, ri, xi)। একটি রাস্তায়, এমন জায়গা আছে যেখানে আমরা ঘর তৈরি করতে পারি। দাগ 1 থেকে n হিসাবে সংখ্যা করা হয়. বাড়ির উচ্চতা 0 থেকে h হতে পারে। প্রতিটি জায়গায় যদি আমরা k উচ্চতার একটি বাড়ি তৈরি করি, তাহলে তা থেকে আমরা k^2 পরিমাণ অর্থ লাভ করব। এম জোন সীমাবদ্ধতা আছে. ith বিধিনিষেধ বলছে:দাগ লি থেকে রি পর্যন্ত সবচেয়ে উঁচু বাড়িটি অবশ্যই xi হতে হবে। আমরা আমাদের লাভ সর্বাধিক করার জন্য বাড়ি তৈরি করতে চাই। আমাদের সর্বোচ্চ সম্ভাব্য মুনাফা খুঁজে বের করতে হবে। আমাদের সর্বোচ্চ লাভ খুঁজে বের করতে হবে।

সুতরাং, যদি ইনপুট n =3 এর মত হয়; h =3; T =[[1,1,1],[2,2,3],[3,3,2]], তাহলে আউটপুট হবে 14, কারণ, 3টি ঘর আছে, সর্বোচ্চ উচ্চতা 3, প্রথমে 1 এবং 1 এর মধ্যে সবচেয়ে লম্বা বাড়িটিকে সীমাবদ্ধ করুন তাই এটি অবশ্যই 1 হতে হবে। দ্বিতীয় বিধিনিষেধে 2 থেকে 2 এর মধ্যে সবচেয়ে লম্বা বাড়ি এবং এটি অবশ্যই 3টি হতে হবে। একইভাবে তৃতীয় সীমাবদ্ধতায় 3 এবং 3-এর মধ্যে সবচেয়ে লম্বা বাড়ি যা সর্বাধিক 2 হতে হবে। সুতরাং সর্বোত্তম উচ্চতা হল [1,3,2]। তাই 1^2 + 3^2 + 2^2 =14।

পদক্ষেপ

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

m := size of T
Define an array heights n and fill with h
for initialize i := 0, when i < m, update (increase i by 1), do:
   l := T[i, 0]
   r := T[i, 1]
   h := T[i, 2]
   for initialize i := l - 1, when i < r, update (increase i by 1), do:
      heights[i] := minimum of heights[i] and h
ans := 0
for initialize i := 0, when i < n, update (increase i by 1), do:
   ans := ans + heights[i] * heights[i]
return ans

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

#include <bits/stdc++.h>
using namespace std;
int solve(int n, int h, vector<vector<int>> T){
   int l, r;
   int m = T.size();
   vector<int> heights(n, h);
   for (int i = 0; i < m; i++){
      l = T[i][0];
      r = T[i][1];
      h = T[i][2];
      for (int i = l - 1; i < r; i++)
      heights[i] = min(heights[i], h);
   }
   int ans = 0;
   for (int i = 0; i < n; i++)
   ans += heights[i] * heights[i];
   return ans;
}
int main(){
   int n = 3;
   int h = 3;
   vector<vector<int>> T = { { 1, 1, 1 }, { 2, 2, 3 }, { 3, 3, 2 } };
   cout << solve(n, h, T) << endl;
}

ইনপুট

3, 3, { { 1, 1, 1 }, { 2, 2, 3 }, { 3, 3, 2 } }