मान लीजिए हमारे पास दो संख्याएं n और h हैं, और m ट्रिपलेट्स की एक और सरणी T है, जहां T[i] = (li, ri, xi)। एक सड़क पर n स्थान हैं जहां हम घर बना सकते हैं। स्पॉट 1 से n तक नंबर दिए गए हैं। घर की ऊंचाई 0 से h तक हो सकती है। प्रत्येक स्पॉट पर यदि हम ऊंचाई k का घर बनाते हैं, तो हमें उससे k^2 राशि का पैसा मिलेगा। m ज़ोन प्रतिबंध हैं। i-वां प्रतिबंध कहता है: स्पॉट li से ri तक का सबसे ऊंचा घर अधिकतम 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 } }आउटपुट
14
