Số ngày nghỉ tối đa trong C ++

Giả sử một công ty muốn cho một trong những nhân viên giỏi nhất của mình lựa chọn đi du lịch giữa N thành phố để thu thập một số tài nguyên. Nhưng nhân viên cũng muốn có một số kỳ nghỉ, chúng tôi có thể đi nghỉ ở một số thành phố và tuần cụ thể. Nhiệm vụ của chúng tôi là lên lịch cho chuyến du lịch để tối đa hóa số ngày nghỉ phép mà chúng tôi có thể thực hiện, nhưng có một số quy tắc và hạn chế nhất định mà chúng tôi phải tuân theo.

Chúng tôi chỉ có thể đi du lịch giữa N thành phố; chúng được đại diện bởi các chỉ mục từ 0 đến N-1. Thứ nhất, chúng tôi ở thành phố được lập chỉ mục 0 vào thứ Hai.
Các thành phố này được kết nối với nhau bằng các chuyến bay. Chúng ta có một ma trận N x N (không nhất thiết đối xứng) để biểu diễn các chuyến bay. Các chuyến bay đại diện cho tình trạng của hãng hàng không từ thành phố i đến thành phố j. Nếu không có chuyến bay nào từ thành phố i đến thành phố j, thì các chuyến bay ma trận [i] [j] sẽ là 0; Nếu không, các chuyến bay [i] [j] =1. Ngoài ra, các chuyến bay [i] [i] =0 cho tất cả tôi.
Chúng tôi có K tuần để đi du lịch. Chúng tôi chỉ có thể thực hiện các chuyến bay nhiều nhất một lần mỗi ngày và chỉ có thể thực hiện các chuyến bay vào sáng Thứ Hai của mỗi tuần.
Đối với mỗi thành phố, chúng ta chỉ có thể có số ngày nghỉ phép hạn chế trong các tuần khác nhau, vì vậy chúng ta có ma trận N * K được gọi là số ngày, điều này thể hiện mối quan hệ này. Đối với giá trị của ngày [i] [j], nó đại diện cho số ngày tối đa chúng tôi có thể đi nghỉ ở thành phố tôi trong tuần j.

Vì vậy, nếu chúng ta có ma trận chuyến bay và ma trận ngày và chúng ta cần xuất số ngày nghỉ tối đa mà chúng ta có thể có trong K tuần.

Vì vậy, nếu đầu vào là các chuyến bay =[[0,1,1], [1,0,1], [1,1,0]], ngày =[[1,3,1], [6,0 , 3], [3,3,3]], thì đầu ra sẽ là 12

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

n:=hàng chuyến bay
m:=các cột của ma trận ngày
Xác định một mảng 2D dp có kích thước (m + 1) x n
để khởi tạo i:=m - 1, khi i> =0, cập nhật (giảm i đi 1), thực hiện -
- để khởi tạo j:=0, khi j
  - để khởi tạo k:=0, khi k
    - nếu j giống với k hoặc các chuyến bay [j, k] khác 0 thì -
      - dp [i, j]:=tối đa của dp [i, j] và ngày [j, i] + dp [i + 1, k]
ret:=dp [0, 0]
để khởi tạo i:=1, khi i
- nếu các chuyến bay [0, i] khác 0 thì -
  - ret:=tối đa ret và dp [0, i]
trả lại ret

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

v1 = {{0,1,1},{1,0,1},{1,1,0}}, v2 = {{1,3,1},{6,0,3},{3,3,3}}

Số ngày nghỉ tối đa trong C ++

Ví dụ

Đầu vào

Đầu ra