두 개의 숫자 n과 h와 T[i] =(li, ri, xi)인 m개의 삼중항 T의 또 다른 배열이 있다고 가정합니다. 길 위에 집을 지을 수 있는 곳은 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