সি++-এ k দিনে জব কমপ্লিট করাতে ন্যূনতম ডিফিকাল্টি যোগফল

সমস্যা বিবরণ

একটি জব লিস্ট jobs এবং দিন সংখ্যা k দেওয়া আছে। জবগুলো ক্রমমতো k দিনে শেষ করতে হবে। প্রতিটি দিনে কমপক্ষে একটি জব করতে হবে। এক দিনের ডিফিকাল্টি = ঐ দিনের সর্বোচ্চ ডিফিকাল্টি वाले জব। সর্বোচ্চ ডিফিকাল্টি যোগফল ন্যূনতম করতে হবে।

উদাহরণ: jobs = [2,3,4,6,3], k = 2 → আউটপুট 8। প্রথম দিন [2] (ডিফিকাল্টি ২), দ্বিতীয় দিন [3,4,6,3] (ডিফিকাল্টি ৬) → মোট ৮।

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

ডাইনামিক প্রোগ্রামিং + মেমোইজেশন:

1. dfs(start, k) = ইনডেক্স start থেকে শুরু করে k দিনে বাকি জব কমপ্লিট করার ন্যূনতম ডিফিকাল্টি।
2. বেস কেস: start >= n → k==0 ? 0 : INF।
3. ট্রানজিশন: i = start থেকে n-1 পর্যন্ত লুপ চালিয়ে val = max(val, jobs[i]) এবং ret = min(ret, val + dfs(i+1, k-1))।
4. মেমোইজেশন দিয়ে dp[start][k] সংরক্ষণ করুন।

উদাহরণ কোড

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e6;
int dp[505][15];

int dfs(int start, int k, vector<int>& v) {
    if (start >= v.size()) return k == 0 ? 0 : INF;
    if (k < 0) return INF;
    if (dp[start][k] != -1) return dp[start][k];
    int ret = INF, val = 0;
    for (int i = start; i < v.size(); i++) {
        val = max(val, v[i]);
        ret = min(ret, val + dfs(i+1, k-1, v));
    }
    return dp[start][k] = ret;
}

int solve(vector<int>& jobs, int k) {
    memset(dp, -1, sizeof dp);
    return dfs(0, k, jobs);
}

int main() {
    vector<int> v = {2, 3, 4, 6, 3};
    int k = 2;
    cout << solve(v, k);
    return 0;
}

ইনপুট ও আউটপুট

ইনপুট: {2,3,4,6,3}, 2

আউটপুট: 8