数据结构
网络
关系型数据库管理系统
操作系统
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 次浏览
广告