Mã C ++ để nhận lợi nhuận tối đa bằng cách tạo ra từng nhà

Giả sử chúng ta có hai số n và h, và một mảng khác gồm m bộ ba T, trong đó T [i] =(li, ri, xi). Trên một con đường, có n nơi chúng ta có thể làm nhà. Các điểm được đánh số từ 1 đến n. Chiều cao nhà có thể từ 0 đến h. Tại mỗi vị trí nếu chúng ta làm một ngôi nhà có chiều cao k, chúng ta sẽ thu được k ^ 2 số tiền từ nó. Có m giới hạn vùng. Hạn chế thứ i cho biết:Ngôi nhà cao nhất từ ​​điểm li đến điểm ri, tối đa phải bằng xi. Chúng tôi muốn làm nhà để tối đa hóa lợi nhuận của chúng tôi. Chúng ta phải tìm ra mức lợi nhuận tối đa mà chúng ta có thể tạo ra. Chúng ta phải tìm ra lợi nhuận tối đa.

Vì vậy, nếu đầu vào giống như n =3; h =3; T =[[1,1,1], [2,2,3], [3,3,2]], thì đầu ra sẽ là 14, bởi vì, có 3 ngôi nhà, chiều cao tối đa là 3, Trong giới hạn đầu tiên ngôi nhà cao nhất trong khoảng từ 1 đến 1 vì vậy nó phải là 1 ở mức tối đa. Trong giới hạn thứ hai, ngôi nhà cao nhất trong khoảng từ 2 đến 2 và tối đa phải là 3. Tương tự trong giới hạn thứ ba, ngôi nhà cao nhất từ ​​3 đến 3 phải bằng 2. Vì vậy, chiều cao tối ưu là [1,3,2]. Vậy 1 ^ 2 + 3 ^ 2 + 2 ^ 2 =14.

Các bước

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

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

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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;
}

Đầu vào

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

Đầu ra

14