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