C++ এ সবচেয়ে লম্বা বিলবোর্ড

ধরুন আমরা একটি বিলবোর্ড ইন্সটল করছি এবং আমরা এটির উচ্চতা চাই। বিলবোর্ডের দুই পাশে দুটি স্টিল সাপোর্ট থাকবে। প্রতিটি সমর্থন সমান উচ্চতা হতে হবে। আমাদের কাছে রডের একটি সংগ্রহও রয়েছে যা একসাথে ঝালাই করা যায়। সুতরাং, যদি আমাদের 1, 2, এবং 3 দৈর্ঘ্যের রড থাকে, আমরা 6 দৈর্ঘ্যের একটি সমর্থন তৈরি করতে সেগুলিকে একত্রে ঝালাই করতে পারি। আমাদের বিলবোর্ড স্থাপনের সবচেয়ে বড় সম্ভাব্য উচ্চতা খুঁজে বের করতে হবে। যদি আমরা বিলবোর্ড সমর্থন করতে না পারি, 0 ফেরত দিন।

সুতরাং, ইনপুট যদি [1,2,2,3,3,3,4] এর মত হয়, তাহলে আউটপুট হবে 9, যেমন আমাদের উপসেট আছে [1,2,2,4] এবং [3,3, 3]।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

যোগফল :=0, n :=রডের আকার, N :=2 * 5000
একটি 2D অ্যারে 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}