ধরুন একটি কোম্পানি তার সেরা কর্মচারীদের একজনকে কিছু সম্পদ সংগ্রহ করতে N শহরগুলির মধ্যে ভ্রমণ করার বিকল্প দিতে চায়। কিন্তু কর্মীরা কিছু ছুটি চান, আমরা কিছু নির্দিষ্ট শহর এবং সপ্তাহগুলিতে ছুটি নিতে পারি। আমাদের কাজ হল ভ্রমণের সময়সূচী করা যাতে আমরা যতগুলি ছুটি কাটাতে পারি তার সংখ্যা বাড়ানো, তবে কিছু নিয়ম এবং বিধিনিষেধ আমাদের অনুসরণ করতে হবে।
-
আমরা শুধুমাত্র N শহরের মধ্যে ভ্রমণ করতে পারি; তারা 0 থেকে N-1 পর্যন্ত সূচক দ্বারা প্রতিনিধিত্ব করা হয়। প্রথমত, আমরা সোমবার শহরে ০ সূচকে আছি।
-
এই শহরগুলি ফ্লাইটের মাধ্যমে সংযুক্ত। ফ্লাইটগুলিকে উপস্থাপন করার জন্য আমাদের কাছে একটি N x N ম্যাট্রিক্স (অগত্যা প্রতিসম নয়) আছে। শহর i থেকে শহর j পর্যন্ত এয়ারলাইন স্ট্যাটাস প্রতিনিধিত্বকারী ফ্লাইটগুলি। যদি শহর i থেকে শহর j-এ কোনো ফ্লাইট না থাকে, তাহলে ম্যাট্রিক্স ফ্লাইট[i][j] হবে 0; অন্যথায়, ফ্লাইট[i][j] =1. এছাড়াও, ফ্লাইট[i][i] =0 সবার জন্য।
-
আমাদের ভ্রমণের জন্য K সপ্তাহ আছে। আমরা প্রতিদিন সর্বাধিক একবার ফ্লাইট নিতে পারি এবং শুধুমাত্র প্রতি সপ্তাহের সোমবার সকালে ফ্লাইট নিতে পারি।
-
প্রতিটি শহরের জন্য, আমরা বিভিন্ন সপ্তাহে শুধুমাত্র ছুটির দিনগুলি সীমিত রাখতে পারি, এর জন্য আমাদের কাছে একটি N*K ম্যাট্রিক্স আছে যাকে বলা হয় দিনগুলি এই সম্পর্কটি দেখাচ্ছে৷ দিনের মূল্যের জন্য [i][j], এটি প্রতিনিধিত্ব করে যে আমরা j সপ্তাহে i শহরে ছুটি কাটাতে পারি।
তাই যদি আমাদের ফ্লাইট ম্যাট্রিক্স এবং দিনের ম্যাট্রিক্স থাকে এবং আমাদের K সপ্তাহের মধ্যে সর্বোচ্চ ছুটির দিনগুলি আউটপুট করতে হবে৷
সুতরাং, যদি ইনপুট ফ্লাইটের মত হয় =[[0,1,1],[1,0,1],[1,1,0]], দিন =[[1,3,1],[6,0 ,3],[3,3,3]], তাহলে আউটপুট হবে 12
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
n :=ফ্লাইটের সারি
-
m :=দিনের ম্যাট্রিক্সের কলাম
-
আকারের একটি 2D অ্যারে ডিপি (m + 1) x n
সংজ্ঞায়িত করুন -
আরম্ভ করার জন্য i :=m - 1, যখন i>=0, আপডেট করুন (i 1 দ্বারা কম করুন), −
-
j শুরু করার জন্য :=0, যখন j
-
আরম্ভ করার জন্য k :=0, যখন k
-
যদি j হয় k বা ফ্লাইট[j, k] অ-শূন্য হয়, তাহলে −
-
dp[i, j] :=সর্বাধিক dp[i, j] এবং দিন[j, i] + dp[i + 1, k]
-
-
-
-
-
ret :=dp[0, 0]
-
আরম্ভ করার জন্য i :=1, যখন i
-
যদি ফ্লাইট[0, i] অ-শূন্য হয়, তাহলে -
-
ret :=সর্বোচ্চ ret এবং dp[0, i]
-
-
-
রিটার্ন রিটার্ন
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#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;
}
};
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
