C++-এ সর্বোচ্চ বকাশের দিন (Maximum Vacation Days)

এক কোম্পানি তার সেরা কর্মচারীদের N শহরের মধ্যে ভ্রমণ করার সুযোগ দিচ্ছে। কর্মচারীরা নির্দিষ্ট শহর এবং সপ্তাহে বকাশ নিতে চান। লক্ষ্য হল K সপ্তাহে সর্বোচ্চ বকাশের দিন বের করা, কিছু নিয়ম মানেই।

N শহর আছে (ইন্ডেক্স ০ থেকে N-1)। শুরুতে সোমবারে শহর ০-এ থাকবেন।
শহরগুলোর মধ্যে ফ্লাইট সংযোগ আছে, N x N ম্যাট্রিক্সে প্রকাশিত। flights[i][j] = 1 হলে i থেকে j-এ ফ্লাইট আছে, 0 হলে নেই। flights[i][i] = 0।
K সপ্তাহ ভ্রমণ করা যাবে। প্রতিসপ্তাহ সোমবারে সকালে সর্বোচ্চ একবার ফ্লাইট নেওয়া যাবে।
প্রতিটি শহরে প্রতিটি সপ্তাহে বকাশের দিন নির্ধারিত, days[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]] হলে আউটপুট ১২।

সমাধানের ধাপসমূহ

n := flights-র সারি সংখ্যা
m := days-র কলাম সংখ্যা
dp অ্যারে (m+1) x n আকারে সংজ্ঞায়িত করুন
i := m-1 থেকে ০ পর্যন্ত লুপ:
- j := 0 থেকে n-1 পর্যন্ত লুপ:
  - k := 0 থেকে n-1 পর্যন্ত লুপ:
    - যদি j==k বা flights[j][k] != 0 হয়, 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] != 0 হয়, 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}}