数据结构
网络
关系数据库管理系统
操作系统
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 次查看
