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; } }
查看更多题解地址