Billboard cao nhất trong C ++

Giả sử chúng ta đang lắp đặt một bảng quảng cáo và chúng tôi muốn nó có chiều cao lớn nhất. Bảng quảng cáo sẽ có hai giá đỡ bằng thép ở hai bên. Mỗi giá đỡ phải có chiều cao bằng nhau. Chúng tôi cũng có một bộ sưu tập các thanh có thể được hàn lại với nhau. Vì vậy, nếu chúng ta có các thanh có độ dài 1, 2 và 3, chúng ta có thể hàn chúng lại với nhau để tạo thành giá đỡ có độ dài 6. Chúng ta phải tìm chiều cao lớn nhất có thể cho việc lắp đặt biển quảng cáo của chúng ta. Nếu chúng tôi không thể hỗ trợ bảng quảng cáo, hãy trả lại 0.

Vì vậy, nếu đầu vào là [1,2,2,3,3,3,4], thì đầu ra sẽ là 9, vì chúng ta có các tập con như [1,2,2,4] và [3,3, 3].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• sum:=0, n:=kích thước của thanh, N:=2 * 5000

• Xác định một mảng 2D dp (n + 1) x (N + 1, -1)

• dp [0, 5000]:=0

• để khởi tạo i:=0, khi i

  • để khởi tạo j:=0, khi j <=N, cập nhật (tăng j lên 1), thực hiện -

    • x:=que [i]

    • nếu j - x> =0 và dp [i, j - x] không bằng -1 thì -

      • dp [i + 1, j] =max của dp [i + 1, j] và dp [i, j - x] + x

    • nếu j + x <=N và dp [i, j + x] không bằng -1 thì -

      • dp [i + 1, j] =max của dp [i + 1, j] và dp [i, j + x]

    • nếu dp [i, j] không bằng -1 thì

      • dp [i + 1, j] =max của dp [i, j] và dp [i + 1, j]

• trả về dp [n, 5000]

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

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

Đầu ra

9