ধরুন আমাদের কাছে অনন্য এবং সাজানো সংখ্যার একটি তালিকা রয়েছে যা একটি স্ট্রিংয়ে ব্রেকপয়েন্টগুলিকে উপস্থাপন করে। আমরা এই নিয়মগুলি থেকে একটি গাছ তৈরি করতে চাই -
-
এমন নোড আছে যেগুলির একটি মান (a, b) আছে যেখানে a এবং b ব্রেকপয়েন্ট। এর মানে হল স্ট্রিং এর মধ্যে সূচক [a, b] থেকে নোড বিস্তৃত।
-
রুট নোড প্রতিটি ব্রেকপয়েন্ট জুড়ে বিস্তৃত। (পুরো স্ট্রিং)।
-
একটি নোডের বাম এবং ডান সন্তানের স্প্যানগুলি ক্রমানুসারে, সংলগ্ন এবং প্যারেন্ট নোডের স্প্যান ধারণ করে৷
-
ব্রেকপয়েন্টে 'a'-এর লিফ নোডের সূচক ব্রেকপয়েন্টে 'b'-এর সূচকের আগে 1।
গাছের প্রতিটি নোডের জন্য b - a এর যোগফল হিসাবে একটি গাছের মূল্য নির্ধারণ করা হয়। আমাদের লক্ষ্য হল একটি সম্ভাব্য গাছের সম্ভাব্য সর্বনিম্ন মূল্য নির্ধারণ করা।
সুতরাং, যদি ইনপুট ব্রেকপয়েন্টের মত হয় =[1, 4, 7, 12], তাহলে আউটপুট হবে 28।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
n :=ইনপুট অ্যারে ব্রেকপয়েন্টের আকার
-
যদি n <=1 হয়, তাহলে −
-
রিটার্ন 0
-
-
যদি n 2 এর সমান হয়, তাহলে −
-
রিটার্ন ব্রেকপয়েন্ট[1] - ব্রেকপয়েন্ট[0]
-
-
একটি অ্যারে সংজ্ঞায়িত করুন p[n - 1]
-
আরম্ভ করার জন্য i :=0, যখন i
-
p[i] :=ব্রেকপয়েন্ট[i + 1]
-
-
একটি অ্যারে পূর্ব[n]
সংজ্ঞায়িত করুন -
আরম্ভ করার জন্য i :=1, যখন i
-
pre[i] :=pre[i - 1] + p[i - 1]
-
-
একটি 2D অ্যারে dp[n, n] সংজ্ঞায়িত করুন এবং অসীম সহ কলামগুলি শুরু করুন৷
-
একটি 2D অ্যারে op[n, n]
সংজ্ঞায়িত করুন -
আরম্ভ করার জন্য i :=1, যখন i
-
dp[i,i] :=p[i - 1], op[i,i] :=i
-
-
শুরু করার জন্য len :=2, যখন len
-
আরম্ভ করার জন্য i :=1, যখন i + len - 1
-
j :=i + len - 1
-
idx :=i
-
আরম্ভ করার জন্য k :=সর্বাধিক (i, op[i,j-1]), যখন k <সর্বনিম্ন (j - 1, op[i + 1, j]), আপডেট করুন (k 1 দ্বারা বৃদ্ধি করুন), করবেন −
-
খরচ :=dp[i, k] + dp[k + 1, j]
-
যদি খরচ হয়
-
idx :=k
-
dp[i, j] :=খরচ
-
-
-
op[i, j] :=idx
-
dp[i, j] :=dp[i, j] + pre[j] - pre[i - 1]
-
-
-
রিটার্ন dp[1, n - 1]
উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
#include <bits/stdc++.h>
using namespace std;
int solve(vector<int>& breakpoints) {
int n = breakpoints.size();
if (n <= 1) return 0;
if (n == 2) return breakpoints[1] - breakpoints[0];
vector<int> p(n - 1);
for (int i = 0; i < n - 1; ++i) p[i] = breakpoints[i + 1] - breakpoints[i];
vector<int> pre(n);
for (int i = 1; i < n; ++i) pre[i] = pre[i - 1] + p[i - 1];
vector<vector<int>> dp(n, vector<int>(n, INT_MAX));
vector<vector<int>> op(n, vector<int>(n));
for (int i = 1; i < n; ++i) dp[i][i] = p[i - 1], op[i][i] = i;
for (int len = 2; len < n; ++len) {
for (int i = 1; i + len - 1 < n; ++i) {
int j = i + len - 1;
int idx = i;
for (int k = max(i, op[i][j - 1]); k <= min(j - 1, op[i + 1][j]); ++k) {
int cost = dp[i][k] + dp[k + 1][j];
if (cost < dp[i][j]) {
idx = k;
dp[i][j] = cost;
}
}
op[i][j] = idx;
dp[i][j] += pre[j] - pre[i - 1];
}
}
return dp[1][n - 1];
}
int main(){
vector<int> breakpoints = {1, 4, 7, 12};
cout << solve(breakpoints) << endl;
return 0;
} ইনপুট
{1, 4, 7, 12} আউটপুট
28
