家づくりで最大の利益を得るためのC++コード

2つの数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から2の間の最も高い家で、最大で3でなければなりません。同様に、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