首页 > 试题广场 >

假期

[编程题]假期

热度指数：7721 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

由于业绩优秀，公司给小Q放了 n 天的假，身为工作狂的小Q打算在在假期中工作、锻炼或者休息。他有个奇怪的习惯：不会连续两天工作或锻炼。只有当公司营业时，小Q才能去工作，只有当健身房营业时，小Q才能去健身，小Q一天只能干一件事。给出假期中公司，健身房的营业情况，求小Q最少需要休息几天。

输入描述:

第一行一个整数  表示放假天数
第二行 n 个数 每个数为0或1,第 i 个数表示公司在第 i 天是否营业
第三行 n 个数 每个数为0或1,第 i 个数表示健身房在第 i 天是否营业
（1为营业 0为不营业）

输出描述:

一个整数，表示小Q休息的最少天数

示例1

输入

4
1 1 0 0
0 1 1 0

输出

说明

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

算法知识视频讲解

JavaScript

今天打工了吗

参考评论中动归思路，仿照写了javascript代码，值得注意的是js需创建dp二维数组。

    let nDayoff = readline();
    let workStr = readline();
    let gymStr = readline();

    let work = workStr.split(' ').map(Number);
    let gym = gymStr.split(' ').map(Number);
    let len = work.length;
    
    let dp = new Array(nDayoff + 1);
    for (let i = 0; i < nDayoff + 1; i++) {
        dp[i] = new Array(3).fill(Infinity);
    }
    //console.log("dp:", dp);

    dp[0][0] = dp[0][1] = dp[0][2] = 0;
    for (let i = 1; i <= len; i++) {
        if (gym[i - 1] === 1) {
            // 可以锻炼
            dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]);
        }
        if (work[i - 1] === 1) {
            //可以工作
            dp[i][2] = Math.min(dp[i - 1][0], dp[i - 1][1]);
        }
        //可以休息
        dp[i][0] = Math.min(dp[i - 1][0], Math.min(dp[i - 1][1], dp[i - 1][2])) + 1;
    }
    let res = Math.min(dp[len][0], Math.min(dp[len][1], dp[len][2]));
    console.log(res);

发表于 2020-08-25 15:52:52 回复(0)