資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中的最大假期天數
假設一家公司想給其中一位表現最好的員工提供一個機會，讓他在 N 個城市之間旅行以收集一些資源。但員工也想要一些假期，我們可以在某些特定的城市和周內休假。我們的任務是安排旅行，以最大化我們可以休假的假期天數，但我們必須遵循某些規則和限制。
我們只能在 N 個城市之間旅行；它們由索引 0 到 N-1 表示。首先，我們在週一位於索引為 0 的城市。
這些城市之間透過航班連線。我們有一個 N x N 矩陣（不一定是對稱的）來表示航班。航班表示從城市 i 到城市 j 的航空狀態。如果沒有從城市 i 到城市 j 的航班，則矩陣 flights[i][j] 將為 0；否則，flights[i][j] = 1。此外，對於所有 i，flights[i][i] = 0。
我們有 K 周的時間旅行。我們每天最多隻能乘坐一次航班，並且只能在每週星期一的早上乘坐航班。
對於每個城市，我們每星期只能有有限的假期天數，為此我們有一個 N*K 矩陣稱為 days，它顯示了這種關係。對於 days[i][j] 的值，它表示我們在第 j 周的城市 i 中可以休假的最大天數。
因此，如果我們有 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 的二維陣列 dp
初始化 i := m - 1，當 i >= 0 時，更新（將 i 減 1），執行 -
初始化 j := 0，當 j < n 時，更新（將 j 加 1），執行 -
初始化 k := 0，當 k < n 時，更新（將 k 加 1），執行 -
如果 j 與 k 相同或 flights[j, k] 非零，則 -
dp[i, j] := dp[i, j] 和 days[j, i] + dp[i + 1, k] 的最大值
ret := dp[0, 0]
初始化 i := 1，當 i < n 時，更新（將 i 加 1），執行 -
如果 flights[0, i] 非零，則 -
ret := 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;
}
};
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
354 次檢視
