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

Mô tả bài toán

Một công ty cho phép nhân viên du lịch giữa N thành phố (chỉ số 0 đến N-1). Ban đầu ở thành phố 0 vào thứ Hai. Các thành phố kết nối bởi chuyến bay (ma trận flights kích thước N×N, flights[i][j] = 1 nếu có bay từ i đến j, ngược lại 0; flights[i][i] = 0). Có K tuần để du lịch, chỉ được bay tối đa 1 lần/ngày và chỉ vào sáng thứ Hai mỗi tuần. Ma trận days kích thước N×K, days[i][j] là số ngày nghỉ tối đa tại thành phố i tuần j. Tìm tổng ngày nghỉ lớn nhất có thể đạt được.

Ví dụ: flights = [[0,1,1],[1,0,1],[1,1,0]], days = [[1,3,1],[6,0,3],[3,3,3]] → Đầu ra: 12.

Ý tưởng giải pháp (Quy hoạch động)

dp[i][j] = số ngày nghỉ lớn nhất từ tuần i đến hết, nếu bắt đầu tuần i ở thành phố j.
Khởi tạo dp[K][*] = 0.
Duyệt ngược tuần i = K-1 ... 0:
- Với mỗi thành phố j, thử ở lại (k = j) hoặc bay đến k (flights[j][k] = 1):
  - dp[i][j] = max(dp[i][j], days[j][i] + dp[i+1][k])
Kết quả: max(dp[0][0], dp[0][i] với flights[0][i] = 1).

Ví dụ minh họa

#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, 0));
        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 = 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);
    return 0;
}

Đầu vào

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