资讯专栏INFORMATION COLUMN

[LeetCode] 568. Maximum Vacation Days

468122151 / 1582人阅读

Problem

LeetCode wants to give one of its best employees the option to travel among N cities to collect algorithm problems. But all work and no play makes Jack a dull boy, you could take vacations in some particular cities and weeks. Your job is to schedule the traveling to maximize the number of vacation days you could take, but there are certain rules and restrictions you need to follow.

Rules and restrictions:
You can only travel among N cities, represented by indexes from 0 to N-1. Initially, you are in the city indexed 0 on Monday.
The cities are connected by flights. The flights are represented as a N*N matrix (not necessary symmetrical), called flights representing the airline status from the city i to the city j. If there is no flight from the city i to the city j, flightsi = 0; Otherwise, flightsi = 1. Also, flightsi = 0 for all i.
You totally have K weeks (each week has 7 days) to travel. You can only take flights at most once per day and can only take flights on each week"s Monday morning. Since flight time is so short, we don"t consider the impact of flight time.
For each city, you can only have restricted vacation days in different weeks, given an N*K matrix called days representing this relationship. For the value of daysi, it represents the maximum days you could take vacation in the city i in the week j.
You"re given the flights matrix and days matrix, and you need to output the maximum vacation days you could take during K weeks.

Example 1:

Input:flights = [[0,1,1],[1,0,1],[1,1,0]], days = [[1,3,1],[6,0,3],[3,3,3]]
Output: 12
Explanation: 
Ans = 6 + 3 + 3 = 12. 

One of the best strategies is:
1st week : fly from city 0 to city 1 on Monday, and play 6 days and work 1 day. 
(Although you start at city 0, we could also fly to and start at other cities since it is Monday.) 
2nd week : fly from city 1 to city 2 on Monday, and play 3 days and work 4 days.
3rd week : stay at city 2, and play 3 days and work 4 days.

Example 2:

Input:flights = [[0,0,0],[0,0,0],[0,0,0]], days = [[1,1,1],[7,7,7],[7,7,7]]
Output: 3
Explanation: 
Ans = 1 + 1 + 1 = 3. 

Since there is no flights enable you to move to another city, you have to stay at city 0 for the whole 3 weeks. 
For each week, you only have one day to play and six days to work. 
So the maximum number of vacation days is 3.

Example 3:

Input:flights = [[0,1,1],[1,0,1],[1,1,0]], days = [[7,0,0],[0,7,0],[0,0,7]]
Output: 21
Explanation:
Ans = 7 + 7 + 7 = 21

One of the best strategies is:
1st week : stay at city 0, and play 7 days. 
2nd week : fly from city 0 to city 1 on Monday, and play 7 days.
3rd week : fly from city 1 to city 2 on Monday, and play 7 days.

Note:

N and K are positive integers, which are in the range of [1, 100].
In the matrix flights, all the values are integers in the range of [0, 1].
In the matrix days, all the values are integers in the range [0, 7].
You could stay at a city beyond the number of vacation days, but you should work on the extra days, which won"t be counted as vacation days.
If you fly from the city A to the city B and take the vacation on that day, the deduction towards vacation days will count towards the vacation days of city B in that week.
We don"t consider the impact of flight hours towards the calculation of vacation days.
Solution
class Solution {
    public int maxVacationDays(int[][] flights, int[][] days) {
        //n cities, k weeks
        //flights[i][j] == 1 means there"s a flight from i to j
        //days[i][j] means the j-th week max vacation in city i
        //dp[i][j] means the max vacation to in city i in week j
        int n = flights.length;
        int k = days[0].length;
        int[][] dp = new int[n][k];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dp[i], -1);
        }
        dp[0][0] = days[0][0];
        for (int i = 1; i < n; i++) {
            if (flights[0][i] == 1) {
                dp[i][0] = days[i][0];
            }
        }
        
        for (int week = 1; week < k; week++) {
            for (int dest = 0; dest < n; dest++) {
                for (int depart = 0; depart < n; depart++) {
                    if (dp[depart][week-1] != -1 && (depart == dest || flights[depart][dest] == 1)) {
                        dp[dest][week] = Math.max(dp[dest][week], dp[depart][week-1]+days[dest][week]);
                    }
                }
            }
        }
        
        int res = 0;
        for (int city = 0; city < n; city++) {
            res = Math.max(res, dp[city][k-1]);
        }
        
        return res;
    }
}

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/72113.html

相关文章

  • python字符串的基本语法

    摘要:切片语句的表达式切片字符串是包含的不会取简称顾头不顾尾国庆节快乐定义变量取的第一个字符到第个字符取的第二个字符到第个字符超出范围了是不会报错的切片和索引超出范围是不一样的索引会报错切片不会。 一、标识符 1、标识符包括:变量、项目名、包名(文件夹)、...

    番茄西红柿 评论0 收藏2637
  • [LeetCode] Third Maximum Number

    Problem Given a non-empty array of integers, return the third maximum number in this array. If it does not exist, return the maximum number. The time complexity must be in O(n). Example Example 1: Inp...

    red_bricks 评论0 收藏0
  • [LeetCode] Maximum Binary Tree

    Problem Given an integer array with no duplicates. A maximum tree building on this array is defined as follow: The root is the maximum number in the array.The left subtree is the maximum tree construc...

    xiaoqibTn 评论0 收藏0
  • LeetCode 104 Maximum Depth of Binary Tree 二叉树最大深度

    LeetCode 104 Maximum Depth of Binary Tree难度:Easy 题目描述:找到一颗二叉树的最深深度。Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down ...

    PiscesYE 评论0 收藏0

发表评论

0条评论

468122151

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<