转载

腾讯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可以在第一天工作,第二或者第三健身,最少休息两天

思路

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

d p [ 0 ] [ i ] dp[0][i] , d p [ 1 ] [ i ] dp[1][i] , d p [ 2 ] [ 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 i-1 可以健身或者锻炼才把 d p [ 1 ] [ i ? 1 ] dp[1][i-1] , d p [ 2 ] [ 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();
    }

}
正文到此结束
本文目录