মান লক্ষ্য করুন দুটি সংখ্যা n এবং h, এবং আরেকটি m ট্রিপলেটের অ্যারে T, যেখানে T[i] = (li, ri, xi)। একটি রোডে n জায়গা আছে যেখানে আমরা বাড়ি বানাতে পারি। স্পটগুলো ১ থেকে n নম্বর করা আছে। বাড়ির উঁচু ০ থেকে h হতে পারে। প্রতিটি স্পটে যদি আমরা ক উঁচুতে বাড়ি বানাই, তবে আমরা সেখান থেকে k^2 টাকা লাভ করব। m টি জোন রস্ট্রিকশন আছে। i-তম রস্ট্রিকশন বলে: li থেকে ri স্পট পর্যন্ত সবচেয়ে উঁচু বাড়ি højতো xi হতে পারে। আমরা বাড়ি বানিয়ে আমাদের লাভ সর্বাধিক করতে চাই। আমাদের সর্বাধিক সম্ভাব্য লাভ বের করতে হবে।
তাই, যদি ইনপুট হয় n = 3; h = 3; T = [[1,1,1],[2,2,3],[3,3,2]], তবে আউটপুট হবে ১৪, কারণ, ৩ টি বাড়ি, সর্বোচ্চ উঁচু ৩, প্রথম রস্ট্রিকশনে ১ থেকে ১ পর্যন্ত সর্বোচ্চ উঁচু ১, দ্বিতীয়ে ২ থেকে ২ সর্বোচ্চ ৩, তৃতীয়ে ৩ থেকে ৩ সর্বোচ্চ ২। তাই অপ্টিমাল হাইট [1,3,2]। তাই 1^2 + 3^2 + 2^2 = ১৪।
ধাপসমূহ
এটি সমাধান করার জন্য, আমরা এই ধাপগুলো অনুসরণ করব −
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 } }
আউটপুট
14
