সমস্যা বিবরণ
রড সমূহ দেওয়া থাকলে, সেগুলো বেল্ডিং করে সমান উচ্চতার দুটি সাপোর্ট বানাতে হবে। সর্বোচ্চ সম্ভব উচ্চতা বের করতে হবে। অসম্ভব হলে 0 রিটার্ন করুন।
উদাহরণ
rods = [1,2,2,3,3,3,4] → আউটপুট = 9 (সাবসেট: [1,2,2,4] এবং [3,3,3])
সমাধান পদ্ধতি
- ডাইনামিক প্রোগ্রামিং (DP) ব্যবহার করা হয়।
- dp[i][j] = প্রথম iটি রড দিয়ে হাইট পার্থক্য j-৫০০০ পাওয়ার সর্বোচ্চ কমন হাইট।
- প্রতিটি রডের জন্য: বামে যোগ, ডানে যোগ, বা ব্যবহার না করা — তিনটি অপশন।
- অফসেট ৫০০০ ব্যবহার করে নেগেটিভ ইনডেক্স হ্যান্ডল করা হয়।
C++ বাস্তবায়ন
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int tallestBillboard(vector<int>& rods) {
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];
}
};
int main() {
Solution ob;
vector<int> v = {1,2,2,3,3,3,4};
cout << ob.tallestBillboard(v);
return 0;
}ইনপুট ও আউটপুট
ইনপুট: {1,2,2,3,3,3,4}
আউটপুট: 9
