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