C++で最も高いビルボード

ビルボードを設置していて、それを最大の高さにしたいとします。ビルボードには、両側に2つのスチールサポートがあります。各サポートは同じ高さである必要があります。また、溶接可能なロッドのコレクションもあります。したがって、長さ1、2、および3のロッドがある場合は、それらを溶接して長さ6のサポートを作成できます。ビルボードの設置で可能な限り最大の高さを見つける必要があります。ビルボードをサポートできない場合は、0を返します。

したがって、入力が[1,2,2,3,3,3,4]のような場合、[1,2,2,4]や[3,3、 3]。

これを解決するには、次の手順に従います-

• 合計：=0、n：=ロッドのサイズ、N：=2 * 5000

• 1つの2D配列dp（n + 1）x（N + 1、-1）を定義します

• dp [0、5000]：=0

• 初期化i：=0の場合、i

  • 初期化j：=0の場合、j <=Nの場合、更新（jを1増やします）、実行-

    • x：=ロッド[i]

    • j --x> =0で、dp [i、j --x]が-1に等しくない場合、-

      • dp [i + 1、j] =dp [i + 1、j]およびdp [i、j-x] + x

        の最大値

    • j + x <=Nであり、dp [i、j + x]が-1に等しくない場合、-

      • dp [i + 1、j] =dp [i + 1、j]およびdp [i、j + x]

        の最大値

    • dp [i、j]が-1に等しくない場合、

      • dp [i + 1、j] =dp [i、j]およびdp [i + 1、j]の最大値

• dp [n、5000]

  を返します

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int tallestBillboard(vector<int>& rods){
      int sum = 0;
      int n = rods.size();
      int N = 2 * 5000;
      vector<vector<int> > dp(n + 1, vector<int>(N + 1, -1));
      dp[0][5000] = 0;
      for (int i = 0; i < n; i++) {
         for (int j = 0; j <= N; j++) {
            int x = rods[i];
            if (j - x >= 0 && dp[i][j - x] != -1) {
               dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - x] +
               x);
            }
            if (j + x <= N && dp[i][j + x] != -1) {
               dp[i + 1][j] = max(dp[i + 1][j], dp[i][j + x]);
            }
            if (dp[i][j] != -1) {
               dp[i + 1][j] = max(dp[i][j], dp[i + 1][j]);
            }
         }
      }
      return dp[n][5000];
   }
};
main(){
   Solution ob;
   vector<int> v = {1,2,2,3,3,3,4};
   cout << (ob.tallestBillboard(v));
}

入力

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

出力

9