한 회사에서 최고의 직원 중 한 명에게 자원을 수집하기 위해 N 도시를 여행할 수 있는 옵션을 제공하려고 한다고 가정합니다. 그러나 직원들은 휴가도 원합니다. 우리는 특정 도시와 몇 주에 휴가를 갈 수도 있습니다. 우리의 임무는 휴가 일수를 최대화하기 위해 여행 일정을 잡는 것이지만 따라야 할 특정 규칙과 제한 사항이 있습니다.
-
N개의 도시만 여행할 수 있습니다. 0에서 N-1까지의 인덱스로 표시됩니다. 첫째, 우리는 월요일에 색인이 0인 도시에 있습니다.
-
이 도시들은 항공편으로 연결됩니다. 비행을 나타내는 하나의 N x N 행렬(반드시 대칭일 필요는 없음)이 있습니다. 도시 i에서 도시 j까지의 항공사 상태를 나타내는 항공편. 도시 i에서 도시 j로 가는 비행이 없다면, 행렬 flight[i][j]는 0이 될 것입니다; 그렇지 않으면, flight[i][j] =1입니다. 또한 모든 i에 대해 flight[i][i] =0입니다.
-
K 주 동안 여행해야 합니다. 항공편은 하루에 최대 한 번만 이용할 수 있으며 매주 월요일 아침에만 항공편을 이용할 수 있습니다.
-
각 도시에 대해 다른 주의 휴가일만 제한할 수 있습니다. 이 관계를 보여주는 일이라는 N*K 행렬이 있기 때문입니다. days[i][j] 값의 경우 j 주에 i 도시에서 휴가를 보낼 수 있는 최대 일수를 나타냅니다.
그래서 만약 우리가 Flights Matrix와 Days Matrix를 가지고 있고 K주 동안 사용할 수 있는 최대 휴가 일수를 출력해야 한다면.
따라서 입력이 Flights =[[0,1,1],[1,0,1],[1,1,0]], days =[[1,3,1],[6,0 ,3],[3,3,3]], 출력은 12
가 됩니다.이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
n :=항공편 행
-
m :=일 행렬의 열
-
(m + 1) x n
크기의 2D 배열 dp 하나를 정의합니다. -
initialize i :=m - 1의 경우 i>=0일 때 업데이트(i를 1만큼 감소), −
-
j 초기화의 경우:=0, j
-
초기화 k :=0의 경우 k
-
j가 k와 같거나 flight[j, k]가 0이 아니면 -
-
dp[i, j] :=최대 dp[i, j] 및 일[j, i] + dp[i + 1, k]
-
-
-
-
-
ret :=dp[0, 0]
-
initialize i :=1의 경우 i
-
flight[0, i]가 0이 아닌 경우 -
-
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