标签搜索

目 录CONTENT

文章目录

腾讯2020校园招聘---假期.md

小小城
2022-05-02 / 0 评论 / 0 点赞 / 9 阅读 / 1,910 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-05-02,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

假期.md
date: 2021-08-22 12:10:21.869
updated: 2021-08-22 12:10:21.869
url: /2021/08/22/腾讯2020校园招聘---假期md
categories:
tags:

腾讯2020校园招聘---假期

@[toc]

一、题目描述

由于业绩优秀,公司给小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

输出例子1:

2

例子说明1:

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

二、题目分析

这显然是一道动规题,我们可以选择让小Q工作或者锻炼的时间最长从而让小Q的休息时间最少

先捋一下动规的步骤:

第⼀步, ⼀定要明确 dp 数组的含义

首先我们需要明确动规的 状态 :显然只有三种状态:工作、锻炼、休息,那么我们怎么在dp数组中表示出来呢??

其实还有一种状态,就是休假的天数,因为天数是在动态变化的,所以也需要记录,而工作、锻炼、休息不会出现连续的锻炼和工作,所以可以用一个二维数组来表示:$dp[i][j]$ $=$ $k$;意思是:在第i天j状态下最小的休息天数

规定:
$dp[i][0]$代表在第i天休息的情况下小Q最少的休息天数;
$dp[i][1]$代表在第i天锻炼的情况下小Q最少的休息天数;
$dp[i][2]$代表在第i天工作的情况下小Q最少的休息天数;

如:dp[3][0] = k;代表第3天休息的情况下小Q的最少休息天数为k;

第⼆步, 定义 base case

dp数组出来了,base case就比较简单了

$dp[0][0] = 0$
$dp[0][1] = 0$
$dp[0][2] = 0$
还没开始休假整个锤子~~~~

第三步, 找状态转移⽅程

到这里我们就需要找状态转移方程

  • $dp[i][0]$:代表当前休息,那么小Q最少的休息天数只能选工作和锻炼最小的加上1,即$dp[i][0] = min(dp[i-1][0],min(dp[i-1][1], dp[i-1][2]))+1;$
  • $dp[i][1] = 0$:代表当前可以锻炼,那么就选工作和休息中可以使休息天数最少的情况$dp[i][1] = min( dp[i-1][0], dp[i-1][2] )$;
  • $dp[i][2] = 0$:同理:$dp[i][2] = min( dp[i-1][0], dp[i-1][1] )$;

最后我们要求的结果就保存在$min(dp[n][0], min(dp[n][1], dp[n][2]))$中

三、代码

# include <iostream>
# include <vector>
# include <limits.h>
using namespace std;
  
int main()
{
    int n ;
    while(cin>>n)
    {
        vector<int> gym(n);
        vector<int>work(n);
        for (int i=0; i<n; ++i )
            cin>>work[i];
        
        for(int i=0; i<n; ++i )
            cin>>gym[i];
        
        vector<vector<int>> dp(n + 1,vector<int>(3,INT_MAX)); // 0是休息,1是锻炼,2是工作
 		dp[0][0] = dp[0][1] = dp[0][2] = 0;
        
        //遍历天数
        for ( int i=1; i<=n; ++i )
        {
            if ( gym[i-1] == 1 )
            {
                // 可以锻炼,选休息和工作最小的
                dp[i][1] = min( dp[i-1][0], dp[i-1][2] );
            }
            if ( work[i-1] == 1 )
            {
                // 可以工作,选休息和锻炼最小的
                dp[i][2] = min( dp[i-1][0], dp[i-1][1] );
            }
			//可以休息,选工作和锻炼最小的 +1
            dp[i][0] = min(dp[i-1][0], min(dp[i-1][1], dp[i-1][2]))+1;
        }
		
		//返回结果
        int res = min(dp[n][0], min(dp[n][1], dp[n][2]));
        cout<<res<<endl;
    }
}
0

评论区