সি++-এ ন্যূনতম পার্সিং ট্রি খুঁজে বের করার প্রোগ্রাম

সমস্যা বিবরণ

আমাদের কাছে একটি ইউনিক এবং সাজানো সংখ্যার তালিকা আছে যা একটি স্ট্রিংয়ের ব্রেকপয়েন্ট উপস্থাপন করে। এই নিয়মগুলো থেকে আমরা একটি ট্রি তৈরি করতে চাই:

• নোডগুলোর একটি মান থাকে (a, b) যেখানে a এবং b ব্রেকপয়েন্ট। এর মানে নোডটি স্ট্রিংয়ের ইনডেক্স [a, b] পর্যন্ত বিস্তৃত।
• রুট নোডটি সব ব্রেকপয়েন্টের ওপর বিস্তৃত (পুরো স্ট্রিং)।
• একটি নোডের বাম এবং ডান চাইল্ডের স্প্যান ক্রমবদ্ধ, সন্নিহিত এবং পেরেন্ট নোডের স্প্যান ধারণ করে।
• লিফ নোডগুলোর 'a' এর ইনডেক্স ব্রেকপয়েন্টে 'b' এর ইনডেক্সের থেকে ১ কম।

একটি ট্রির খরচ নির্ধারণ করা হয় ট্রির প্রতিটি নোডের জন্য (b - a) এর যোগফল থেকে। আমাদের লক্ষ্য হলো একটি সম্ভাব্য ট্রির ন্যূনতম সম্ভাব্য খরচ বের করা।

উদাহরণস্বরূপ, যদি ইনপুট হয় breakpoints = [1, 4, 7, 12], তবে আউটপুট হবে 28।

সমাধানের পদ্ধতি

1. n := breakpoints অ্যারেটির আকার
2. যদি n <= 1, তবে 0 রিটার্ন করুন।
3. যদি n == 2, তবে breakpoints[1] - breakpoints[0] রিটার্ন করুন।
4. p[n-1] অ্যারে সংজ্ঞায়িত করুন।
5. i := 0 থেকে n-2 পর্যন্ত লুপ চালিয়ে p[i] := breakpoints[i+1] - breakpoints[i] সেট করুন।
6. pre[n] অ্যারে সংজ্ঞায়িত করুন এবং প্রিফিক্স যোগফল গণনা করুন।
7. দুটি ২D অ্যারে dp[n][n] (অনন্ত দিয়ে ইনিশিয়ালাইজ) এবং op[n][n] সংজ্ঞায়িত করুন।
8. বেস কেস: i = 1 থেকে n-1 পর্যন্ত dp[i][i] = p[i-1] এবং op[i][i] = i।
9. লেন্থ 2 থেকে n-1 পর্যন্ত বড় করলে ডাইনামিক প্রোগ্রামিং দিয়ে ন্যূনতম খরচ গণনা করুন, নাইভ অপ্টিমাইজেশন (Knuth Optimization) ব্যবহার করে।
10. ফলাফল: 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