สมมติว่าเรามีตัวเลขสองตัว n และ h และอีกอาร์เรย์ของ m triplets T โดยที่ T[i] =(li, ri, xi) บนถนนมีสถานที่ที่เราสามารถสร้างบ้านได้ จุดที่มีหมายเลขเป็น 1 ถึง n ความสูงของบ้านสามารถตั้งแต่ 0 ถึงชั่วโมง ในแต่ละจุด ถ้าเราสร้างบ้านสูง k เราจะได้เงิน k^2 จากมัน มีการจำกัดโซน m ข้อจำกัด ith กล่าวว่า:บ้านที่สูงที่สุดจากจุด li ถึง ri ต้องอยู่ที่มากที่สุด xi เราต้องการสร้างบ้านเพื่อเพิ่มผลกำไรสูงสุด เราต้องหาผลกำไรสูงสุดที่เราสามารถทำได้ เราต้องหากำไรให้ได้มากที่สุด
ดังนั้น ถ้าอินพุตเป็นเหมือน n =3; ชั่วโมง =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
