บิลบอร์ดที่สูงที่สุดใน 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

• กำหนดอาร์เรย์ 2 มิติหนึ่งรายการ 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