C++에서 가장 높은 빌보드

<시간/>

광고판을 설치하고 가장 높은 높이를 원한다고 가정합니다. 빌보드는 양쪽에 두 개의 강철 지지대를 가질 것입니다. 각 지지대는 높이가 같아야 합니다. 우리는 또한 함께 용접할 수 있는 막대 모음을 가지고 있습니다. 따라서 길이가 1, 2, 3인 막대가 있으면 함께 용접하여 길이 6의 지지대를 만들 수 있습니다. 광고판 설치에서 가능한 가장 큰 높이를 찾아야 합니다. 빌보드를 지원할 수 없으면 0을 반환하십시오.

따라서 입력이 [1,2,2,3,3,3,4]와 같으면 출력은 [1,2,2,4] 및 [3,3]과 같은 하위 집합이 있으므로 9가 됩니다. 3].

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

sum :=0, n :=막대의 크기, N :=2 * 5000
하나의 2D 배열 정의 dp(n + 1) x (N + 1, -1)
dp[0, 5000] :=0
initialize 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}