ধরি আমরা d দিনে একটি টাস্ক লিস্ট শিডিউল করতে চাই। টাস্কগুলো ডিপেন্ডেন্ট, অর্থাৎ i-তম টাস্ক করতে হলে 0 <= j < i পরিসরের সব টাস্ক খতম করতে হবে।
প্রতিদিন কমপক্ষে একটি টাস্ক খতম করতে হবে। একটি টাস্ক শিডিউলের কঠিনতা হলো প্রতিদিনের কঠিনতার যোগফল। একটি দিনের কঠিনতা হলো সেই দিন করা টাস্কগুলোর মধ্যে সর্বোচ্চ কঠিনতা।
taskDifficulty নামক একটি ইন্টিজার অ্যারে এবং d দেওয়া আছে। i-তম জবের কঠিনতা taskDifficulty[i]। ন্যূনতম কঠিনতাবিশিষ্ট শিডিউল বের করতে হবে। শিডিউল সম্ভব না হলে -1 ফেরত দিন।
ইনপুট যদি taskDifficulty = [6,5,4,3,2,1], d = 2 হয়, তবে আউটপুট হবে 7, কারণ প্রথম দিনে প্রথম ৫টি জব করা যায় (কঠিনতা ৬), দ্বিতীয় দিনে শেষ জব (কঠিনতা ১), মোট ৭।
সমাধানের ধাপসমূহ
solve() ফাংশন সংজ্ঞায়িত করুন যা v, idx, k, 2D dp নেবে –
যদি idx == v.size() এবং k == 0 হয়, তবে 0 ফেরত দিন
যদি k < 0 বা idx == v.size() এবং k > 0 হয়, তবে 1e6 ফেরত দিন
যদি dp[idx, k] != -1 হয়, তবে dp[idx, k] ফেরত দিন
maxVal := 0, ret := inf
i := idx থেকে v.size()-1 পর্যন্ত লুপ চালান –
maxVal := max(v[i], maxVal)
ret := min(ret, maxVal + solve(v, i + 1, k - 1, dp))
dp[idx, k] := ret
ret ফেরত দিন
মূল পদ্ধতিতে –
n := j এর আকার
যদি d > n হয়, তবে -1 ফেরত দিন
n x (d+1) আকারের 2D dp অ্যারে -1 দিয়ে ফিল করুন
solve(j, 0, d, dp) ফেরত দিন
বेहतर বোঝার জন্য নিচের কোডটি দেখুন –
উদাহরণ
#include <bits/stdc++.h> using namespace std; class Solution { public: int solve(vector<int>& v, int idx, int k, vector<vector<int> >& dp){ if (idx == v.size() && k == 0) return 0; if (k < 0 || idx == v.size() && k > 0) return 1e6; if (dp[idx][k] != -1) return dp[idx][k]; int maxVal = 0; int ret = INT_MAX; for (int i = idx; i < v.size(); i++) { maxVal = max(v[i], maxVal); ret = min(ret, maxVal + solve(v, i + 1, k - 1, dp)); } return dp[idx][k] = ret; } int minDifficulty(vector<int>& j, int d){ int n = j.size(); if (d > n) return -1; vector<vector<int> > dp(n, vector<int>(d + 1, -1)); return solve(j, 0, d, dp); } }; main(){ Solution ob; vector<int> v = {6,5,4,3,2,1}; cout << (ob.minDifficulty(v, 2)); }ইনপুট
{6,5,4,3,2,1}, 2আউটপুট
7
