ধরুন আমাদের কাছে চাকরি নামক সংখ্যার একটি তালিকা আছে এবং আরেকটি মান k আছে। এখন আমরা k বিভিন্ন দিনে সব কাজ শেষ করতে চাই। কাজগুলি অবশ্যই প্রদত্ত ক্রমে সম্পাদন করতে হবে এবং প্রতিটি দিনে আমাদের একটি কাজ সম্পূর্ণ করতে হবে। কাজের অসুবিধা i চাকরিতে সংরক্ষিত থাকে [i] এবং একটি দিনে চাকরির তালিকা সম্পূর্ণ করতে অসুবিধা হবে সেই দিনে সম্পাদিত সর্বাধিক অসুবিধার কাজ। তাই k বিভিন্ন দিনে কাজগুলি সম্পাদন করতে আমাদের ন্যূনতম সমষ্টি খুঁজে বের করতে হবে।
সুতরাং, যদি ইনপুটটি jobs =[2, 3, 4, 6, 3] k =2 এর মত হয়, তাহলে আউটপুট হবে 8, প্রথমে আমরা [2] করি তারপর [3, 4, 6, 3] করি। তাই অসুবিধা হল 2 + সর্বাধিক (3, 4, 6, 3) =8।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- আকারের একটি অ্যারে ডিপি সংজ্ঞায়িত করুন:505 x 15।
- একটি ফাংশন dfs() সংজ্ঞায়িত করুন, এটি স্টার্ট, কে, এবং একটি অ্যারে v,
- যদি শুরু>=v এর আকার হয়, তাহলে −
- রিটার্ন (যদি k 0 এর মত হয়, তাহলে 0, অন্যথায় inf)
- যদি k <0 হয়, তাহলে −
- রিটার্ন ইনফ
- যদি dp[start, k] -1 এর সমান না হয়, তাহলে −
- রিটার্ন dp[start, k]
- ret :=inf
- val :=0
- আরম্ভ করার জন্য i :=শুরু করুন, যখন i
- val :=সর্বোচ্চ val এবং v[i]
- ret :=ret এর সর্বনিম্ন এবং (val + dfs(i + 1, k - 1, v))
উদাহরণ (C++)
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
#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;
int 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);
} ইনপুট
{2, 3, 4, 6, 3}, 2 আউটপুট
8
