資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律學C++程式碼實現房屋建造最大利潤
假設我們有兩個數字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
更新於: 2022年3月30日
246 次瀏覽
廣告