腾讯2020校招笔试题-小Q放假

腾讯2020校招笔试题

题目

公司给小Q放了n天的假,他有个奇怪的习惯:不会连续两天工作或段炼

只有当公司开业,小Q才能去工作,

只有当健身房营业时,小O才能去健身,

小Q一天只能干一件事.给出假期中公司,健身房的营业情兄,求小Q最少需要体息几天

输入描述第ー行一个数表示放假天数n

第二行n个数字，数字为0或者1,第i个数表示公司在第1天是否营业

第三行n个数字，数字为0或者1,第i个数表示健身房在第i天是否营业

（1为营业0为不营业)

example

输入

4 1 1 0 0 0 1 1 0

输出

2 小Q可以在第一天工作，第二或者第三健身，最少休息两天

思路

典型的动态规划题目, 稍微注意一些条件

$dp[0][i]$, $dp[1][i]$, $dp[2][i]$分别代表第i天休息最少休息天数、第i天工作最少休息天数、第i天健身最少休息天数

可以得到以下递推公式

$dp[0][i] = min(dp[0][i-1], dp[1][i-1], dp[2][i-1]) + 1 $

注意只有第$i-1$ 可以健身或者锻炼才把$dp[1][i-1]$, $dp[2][i-1]$考虑进去,下同

$dp[1][i] = min(dp[0][i-1],dp[2][i-1]) $ 只有第i天可以工作，才有此式子

$dp[2][i] = min(dp[0][i-1], dp[1][i-1]) $ 只有第i天可以健身，才有此式子

有了递推公式，码代码只是时间的问题

java AC代码

import java.util.Scanner; import java.io.File; import java.lang.Math; public class Main{ public static void main(String args[]) throws Exception{ //File file = new File("in.txt"); //Scanner sc = new Scanner(file); Scanner sc = new Scanner(System.in); int number = sc.nextInt(); int []keep = new int[number+1]; int []work = new int[number+1]; for(int i = 1; i <= number; i++) work[i] = sc.nextInt(); for(int i = 1; i <= number; i++) keep[i] = sc.nextInt(); int [][] dp = new int[3][number+1]; //第一天休息 dp[0][1] = 1; //第一天工作 if(work[1] == 1) dp[1][1] = 0; else dp[1][1] = number + 1; //第一天健身 if(keep[1] == 1) dp[2][1] = 0; else dp[2][1] = number + 1; for(int i = 2; i <= number; i++) { dp[0][i] = Math.min(Math.min(dp[1][i-1], dp[2][i-1]), dp[0][i-1]) + 1; if (work[i] == 1) { dp[1][i] = Math.min(dp[2][i-1], dp[0][i-1]); }else dp[1][i] = number + 1; if(keep[i] == 1) { dp[2][i] = Math.min(dp[1][i-1], dp[0][i-1]); }else dp[2][i] = number + 1; } System.out.println(Math.min(Math.min(dp[0][number], dp[1][number]), dp[2][number])); sc.close(); } }