C ++中的最长假期天数
假设一家公司希望为其最优秀的员工之一提供在N个城市之间旅行以收集一些资源的选择。但是员工也想要一些假期，我们可以在某些特定城市和几周内休假。我们的任务是安排旅行，以使我们可以休假的天数最大化，但是必须遵守某些规则和限制。
我们只能在N个城市之间旅行；它们由从0到N-1的索引表示。首先，我们星期一在索引为0的城市中。
这些城市由航班连接。我们有一个NxN矩阵（不一定对称）来表示飞行。代表从城市i到城市j的航空公司状态的航班。如果没有从城市i到城市j的航班，则矩阵航班[i][j]将为0；否则，flights[i][j]=1。此外，所有i的flights[i][i]=0。
我们有K周旅行。我们每天最多只能搭乘一次航班，并且只能在每个星期的星期一早晨搭乘航班。
对于每个城市，我们只能在不同的星期中有限制的假期，因为我们有一个N*K矩阵，称为天，这说明了这种关系。对于days[i][j]的值，它表示第j周我们在城市i可以休假的最长时间。
因此，如果我们有排期矩阵和天数矩阵，并且我们需要输出在K周内可以使用的最大休假天数。
因此，如果输入就像排期=[[0,1,1]，[1,0,1]，[1,1,0]]，则天=[[1,3,1]，[6,0，3]，[3,3,3]]，则输出为12
为了解决这个问题，我们将遵循以下步骤-
n：=排航班
m：=天矩阵的列
定义一个尺寸为（m+1）xn的2D数组dp
对于初始化i：=m-1，当i>=0时，更新（将i减1），-
对于初始化k：=0，当k<n时，更新（将k增加1），-
dp[i，j]：=dp[i，j]和天[j，i]+dp[i+1，k]的最大值
如果j与k相同或flights[j，k]不为零，则-
对于初始化j：=0，当j<n时，更新（将j增加1），执行-
ret：=dp[0，0]
对于初始化i：=1，当i<n时，更新（将i增加1），-
ret：=ret和dp[0，i]的最大值
如果flight[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