Google 面试题:最大假期天数(如何获得最长的假期)

LintCode 想让它最好的员工之一选择在 N 个城市间旅行来收集算法问题。但是只工作不玩耍,聪明的孩子也会变傻,你可以在某些特定的城市并且一个星期里去度假。你的工作是安排旅行,尽可能多的假期,但是有一些规则和限制你需要遵守。

规则和限制:
您只能在 1 个城市中旅行,由 0 到 N-1 的索引表示。一开始,你周一在城市 0 。

这些城市都是通过航班连接起来的。这些航班被表示为 N*N 矩阵(非必要对称),称为代表航空公司从城市 i 到 j 城市状态的 flights 矩阵。如果没有从城市 i 到城市 j 的航班,flights[i][j] = 0;否则,flights[i][j]= 1 。还有,flights[i][i] = 0 。

你总共有 K 周(每周有 7 天)旅行。你只能每天最多乘坐一次航班,而且只能在每周一早上乘坐航班。由于飞行时间太短,我们不考虑飞行时间的影响。

对于每个城市,你只能在不同的星期里限制休假日,给定一个命名为 days 的 N*K 矩阵表示这种关系。对于 days[i][j]的值,它表示你可以在 j+1 周的城市 i 里休假的最长天数,你得到的是 flights 矩阵和 days 矩阵,你需要输出你在 K 周期间可以获得的最长假期。

  • N 和 K 是正整数,它们在[1, 100]的范围内。
  • 在 flights 矩阵中,所有的值都是在[0, 1]范围内的整数。
  • 在 days 矩阵中,所有的值都是范围内的整数[0, 7]。
  • 你可以呆在一个超过假期天数的城市,但是你应该多工作几天,这不会算作休假日。
  • 如果你从 A 市飞到 B 市,并在那天休假,那么假期的扣除将计入 B 城市的假期天数。
  • 我们不考虑飞行时间对计算假期的影响。

→点击此处在线做题

样例 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.
	
	因为没有航班可以让你飞到另一个城市,所以你必须在城市里呆 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 天。

[题解]

考点:

dp

题解:
dp[i]表示最后到达 i 城市的最长休假时间。先枚举周数,然后枚举终点,然后是起点,判断是否前往(temp[j] = Math.max(temp[j], dp[k] + days[j][i]);),即是否进行转移。每周更新 dp 数组,最后从 dp 数组选择最大值即可。

public class Solution {
    /**
     * @param flights: the airline status from the city i to the city j
     * @param days: days[i][j] represents the maximum days you could take vacation in the city i in the week j
     * @return: the maximum vacation days you could take during K weeks
     */
    public int maxVacationDays(int[][] flights, int[][] days) {
        // Write your code here
        int N = flights.length;
        int K = days[0].length;
        int[] dp = new int[N];
        Arrays.fill(dp, Integer.MIN_VALUE);
        dp[0] = 0;
        for (int i = 0; i < K; i++) {			//逐渐扩大枚举周
            int[] temp = new int[N];
            Arrays.fill(temp, Integer.MIN_VALUE);
            for (int j = 0; j < N; j++) {			//枚举终点
                for(int k = 0; k < N; k++) {			//枚举起点
                    if (j == k || flights[k][j] == 1) {			//如果城市 k 到城市 j 存在航班
                        temp[j] = Math.max(temp[j], dp[k] + days[j][i]);		//则再对当前答案进行选择,即是否从 k 前往 j
                    }
                }
            }
            dp = temp;
        }
        
        int ans = 0;
        for(int i = 0; i < N; i++){			//最后对 dp 数组筛选最大值即可
            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }
}

查看更多题解地址

Click to rate this post!
[Total: 0 Average: 0]

相关文章

发表评论

您的电子邮箱地址不会被公开。