मान लीजिए एक कंपनी अपने सर्वश्रेष्ठ कर्मचारियों में से एक को N शहरों के बीच यात्रा करके कुछ संसाधन एकत्र करने का विकल्प देना चाहती है। लेकिन कर्मचारी कुछ छुट्टियां भी चाहते हैं, हम कुछ विशेष शहरों और हफ्तों में छुट्टियां ले सकते हैं। हमारा कार्य यात्रा को इस तरह शेड्यूल करना है कि हम K हफ्तों के दौरान अधिकतम छुट्टी के दिन ले सकें, लेकिन कुछ नियम और प्रतिबंध हैं जिनका हमें पालन करना होगा।
- हम केवल N शहरों के बीच यात्रा कर सकते हैं; वे 0 से N-1 तक के इंडेक्स द्वारा दर्शाए जाते हैं। सबसे पहले, हम सोमवार को इंडेक्स 0 वाले शहर में होते हैं।
- ये शहर उड़ानों से जुड़े हुए हैं। हमारे पास एक N x N मैट्रिक्स (जरूरी नहीं कि सममित) है जो उड़ानों को दर्शाता है।
flights[i][j]शहर i से शहर j तक एयरलाइन की स्थिति दर्शाता है। यदि शहर i से शहर j तक कोई उड़ान नहीं है, तो मैट्रिक्सflights[i][j]0 होगा; अन्यथा,flights[i][j] = 1। साथ ही, सभी i के लिएflights[i][i] = 0। - हमारे पास यात्रा के लिए K हफ्ते हैं। हम प्रति दिन अधिकतम एक बार उड़ान ले सकते हैं और केवल प्रत्येक हफ्ते के सोमवार की सुबह उड़ान ले सकते हैं।
- प्रत्येक शहर के लिए, हम अलग-अलग हफ्तों में केवल प्रतिबंधित छुट्टी के दिन ले सकते हैं, इसके लिए हमारे पास N*K मैट्रिक्स
daysहै जो इस संबंध को दर्शाता है।days[i][j]के मान के लिए, यह शहर i में हफ्ते j में हम अधिकतम कितने दिन छुट्टी ले सकते हैं, दर्शाता है।
इसलिए यदि हमारे पास flights मैट्रिक्स और days मैट्रिक्स है, और हमें K हफ्तों के दौरान हम जितने अधिकतम छुट्टी के दिन ले सकते हैं, आउटपुट करना है।
इसलिए, यदि इनपुट flights = [[0,1,1],[1,0,1],[1,1,0]], days = [[1,3,1],[6,0,3],[3,3,3]] जैसा है, तो आउटपुट 12 होगा।
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:
n := flights की पंक्तियाँm := days मैट्रिक्स के कॉलम- आकार
(m+1) x nका एक 2D सरणीdpपरिभाषित करें i := m-1से0तक घटाते हुए लूप चलाएं:j := 0सेn-1तक लूप चलाएं:k := 0सेn-1तक लूप चलाएं:- यदि
j == kयाflights[j][k]शून्येतर है, तो:dp[i][j] := max(dp[i][j], days[j][i] + dp[i+1][k])
- यदि
ret := dp[0][0]i := 1सेn-1तक लूप चलाएं:- यदि
flights[0][i]शून्येतर है, तो:ret := max(ret, dp[0][i])
- यदि
retवापस करें
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
उदाहरण
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int maxVacationDays(vector<vector<int>>& flights, vector<vector<int>>& days) {
int n = flights.size();
int m = days[0].size();
vector<vector<int> > dp(m + 1, vector<int>(n));
for (int i = m - 1; i >= 0; i--) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
if (j == k || flights[j][k]) {
dp[i][j] = max(dp[i][j], days[j][i] + dp[i + 1][k]);
}
}
}
}
int ret = 0;
ret = dp[0][0];
for (int i = 1; i < n; i++) {
if (flights[0][i]) {
ret = max(ret, dp[0][i]);
}
}
return ret;
}
};
int main(){
Solution ob;
vector<vector<int>> v1 = {{0,1,1},{1,0,1},{1,1,0}}, v2 = {{1,3,1},{6,0,3},{3,3,3}};
cout << (ob.maxVacationDays(v1, v2));
}
इनपुट
v1 = {{0,1,1},{1,0,1},{1,1,0}}, v2 = {{1,3,1},{6,0,3},{3,3,3}}
आउटपुट
12