一般公司建设网站布局,企业门户网站模板 下载,做网站公司名字应该用图片吗,WordPress禁止下载文章目录1. 题目2. 解题1. 题目
力扣想让一个最优秀的员工在 N 个城市间旅行来收集算法问题。 但只工作不玩耍#xff0c;聪明的孩子也会变傻#xff0c;所以您可以在某些特定的城市和星期休假。 您的工作就是安排旅行使得最大化你可以休假的天数#xff0c;但是您需要遵守…
文章目录1. 题目2. 解题1. 题目
力扣想让一个最优秀的员工在 N 个城市间旅行来收集算法问题。 但只工作不玩耍聪明的孩子也会变傻所以您可以在某些特定的城市和星期休假。 您的工作就是安排旅行使得最大化你可以休假的天数但是您需要遵守一些规则和限制。
规则和限制
您只能在 N 个城市之间旅行用 0 到 N-1 的索引表示。一开始您在索引为0的城市并且那天是星期一。这些城市通过航班相连。这些航班用 N*N 矩阵 flights不一定是对称的表示flights[i][j] 代表城市i到城市j的航空状态。如果没有城市i到城市j的航班flights[i][j] 0否则flights[i][j] 1。同时对于所有的 iflights[i][i] 0。您总共有 K 周每周7天的时间旅行。您每天最多只能乘坐一次航班并且只能在每周的星期一上午乘坐航班。由于飞行时间很短我们不考虑飞行时间的影响。对于每个城市不同的星期您休假天数是不同的给定一个 N*K 矩阵 days 代表这种限制days[i][j] 代表您在第j个星期在城市i能休假的最长天数。 给定 flights 矩阵和 days 矩阵您需要输出 K 周内可以休假的最长天数。
示例 1:
输入:flights [[0,1,1],[1,0,1],[1,1,0]],
days [[1,3,1],[6,0,3],[3,3,3]]
输出: 12
解释:
Ans 6 3 3 12.
最好的策略之一
第一个星期 : 星期一从城市0飞到城市1玩6天工作1天。
虽然你是从城市0开始但因为是星期一我们也可以飞到其他城市。
第二个星期 : 星期一从城市1飞到城市2玩3天工作4天。
第三个星期 : 呆在城市2玩3天工作4天。示例 2:
输入:flights [[0,0,0],[0,0,0],[0,0,0]],
days [[1,1,1],[7,7,7],[7,7,7]]
输出: 3
解释:
Ans 1 1 1 3.
由于没有航班可以让您飞到其他城市你必须在城市0呆整整3个星期。
对于每一个星期你只有一天时间玩剩下六天都要工作。
所以最大休假天数为3.示例 3:
输入:flights [[0,1,1],[1,0,1],[1,1,0]],
days [[7,0,0],[0,7,0],[0,0,7]]
输出: 21
解释:
Ans 7 7 7 21
最好的策略之一是
第一个星期 : 呆在城市0玩7天。
第二个星期 : 星期一从城市0飞到城市1玩7天。
第三个星期 : 星期一从城市1飞到城市2玩7天。注意:
N 和 K 都是正整数在 [1, 100] 范围内。
矩阵 flights 的所有值都是 [0, 1] 范围内的整数。
矩阵 days 的所有值都是 [0, 7] 范围内的整数。
超过休假天数您仍可以呆在那个城市但是在额外的日子您需要 工作
这些日子不会算做休假日。
如果您从城市A飞往城市B并在当天休假日
这个休假会被算作是城市B的休假日。
我们不考虑飞行时间对计算休假日的影响。来源力扣LeetCode 链接https://leetcode-cn.com/problems/maximum-vacation-days 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
class Solution {
public:int maxVacationDays(vectorvectorint flights, vectorvectorint days) {int dp[100][100];// 在 i 城市时 是第 k 周 最多休假天数memset(dp, 0xff, sizeof(dp));int n flights.size(), k days[0].size(), maxdays 0;for(int i 0; i n; i){//可以待在原地不走flights[i][i] 1;} for(int i 0; i n; i)//初始化第0周{if(flights[0][i])//0城市可以飞到i城市{dp[i][0] days[i][0];maxdays max(maxdays, dp[i][0]);}}for(int wk 1; wk k; wk)//遍历剩余的周{for(int i 0; i n; i)//遍历每个城市{if(dp[i][wk-1] -1)//上周i城市的状态不存在continue;for(int j 0; j n; j)//我要去 j 城市{if(!flights[i][j])//没有航班不行continue;dp[j][wk] max(dp[j][wk], dp[i][wk-1]days[j][wk]);maxdays max(maxdays, dp[j][wk]);}}}return maxdays;}
};276 ms 18.6 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
