C ++中最高的广告牌

假设我们正在安装广告牌，并且希望它具有最大的高度。广告牌的两侧将有两个钢制支撑。每个支架的高度必须相等。我们也提供可以焊接在一起的棒材。因此，如果我们有长度为1、2和3的杆，我们可以将它们焊接在一起以制成长度为6的支撑。我们必须找到广告牌安装的最大高度。如果我们不能支持广告牌，请返回0。

因此，如果输入像[1,2,2,3,3,3,4]，那么输出将为9，因为我们有像[1,2,2,4]和[3,3， 3]。

为了解决这个问题，我们将遵循以下步骤-

• sum：= 0，n：=棒的尺寸，N：= 2 * 5000

• 定义一个2D数组dp（n + 1）x（N + 1，-1）

• dp [0，5000]：= 0

• 对于初始化i：= 0，当i <n时，更新（将i增加1），执行-

• x：=棒[i]

• 如果j-x> = 0并且dp [i，j-x]不等于-1，则-

• 如果j + x <= N并且dp [i，j + x]不等于-1，则-

• 如果dp [i，j]不等于-1，则

• dp [i + 1，j] = dp [i + 1，j]和dp [i，j-x] + x的最大值

• dp [i + 1，j] = dp [i + 1，j]和dp [i，j + x]的最大值

• dp [i + 1，j] = dp [i，j]和dp [i + 1，j]的最大值

• 对于初始化j：= 0，当j <= N时，更新（将j增加1），执行-

• 返回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