मान लीजिए हम कार्यों की एक सूची को d दिनों में शेड्यूल करना चाहते हैं। कार्य निर्भर हैं इसलिए, i-वें कार्य पर काम करने के लिए, हमें उन सभी कार्यों j को पूरा करना होगा जहां 0 <= j < i।
हमें प्रत्येक दिन कम से कम एक कार्य पूरा करना होगा। एक कार्य शेड्यूल की कठिनाई वास्तव में d दिनों में से प्रत्येक दिन की कठिनाइयों का योग है। एक दिन की कठिनाई उस दिन किए गए कार्य की अधिकतम कठिनाई है।
इसलिए हमारे पास taskDifficulty नामक पूर्णांकों की एक सरणी और एक पूर्णांक d है। i-वें कार्य की कठिनाई taskDifficulty[i] है। हमें कार्य शेड्यूल की न्यूनतम कठिनाई ज्ञात करनी है। यदि हम कार्यों के लिए शेड्यूल नहीं ढूंढ सकते, तो -1 लौटाएं।
यदि इनपुट taskDifficulty = [6,5,4,3,2,1], d = 2 है, तो आउटपुट 7 होगा, क्योंकि दिन 1 पर हम पहले 5 कार्य पूरे कर सकते हैं, कुल कठिनाई 6 है। अब दिन 2 पर हम अंतिम कार्य पूरा कर सकते हैं, कुल कठिनाई 1 है, इसलिए शेड्यूल की कठिनाई 6 + 1 = 7 होगी।
हल करने के चरण
solve() फ़ंक्शन परिभाषित करें जो सरणी v, idx, k, 2D dp लेता है
यदि idx == v.size() और k == 0 तो 0 लौटाएं
यदि k < 0 या idx == v.size() और k > 0 तो INF लौटाएं
यदि dp[idx][k] != -1 तो dp[idx][k] लौटाएं
maxVal := 0, ret := INF
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 लौटाएं, dp आरंभ करें, 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);
}
};
int main() {
Solution ob;
vector<int> v = {6,5,4,3,2,1};
cout << (ob.minDifficulty(v, 2));
return 0;
}
इनपुट
{6,5,4,3,2,1}, 2
आउटपुट
7
