您现在的位置:首页 > >

腾讯面试题:假期

发布时间:

题目

时间限制: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

输出例子1:
2

例子说明1:
小Q可以在第一天工作,第二天或第三天健身,小Q最少休息2天

解答

package offer.tengxun;

import java.util.Scanner;

public class Holiday
{
public static void main(String[] args)
{
Scanner in = new Scanner(System.in);
int day=in.nextInt();
in.nextLine();
int[] work=new int[day];
int[] sport=new int[day];
String[] workString = in.nextLine().split(" ");
String[] sportString = in.nextLine().split(" ");
in.close();
for(int x=0;x {
work[x]=Integer.parseInt(workString[x]);
sport[x]=Integer.parseInt(sportString[x]);
}
/*
* 上面将数据准备完毕,然后进行动态规划
* dp[x][0]代表工作
* dp[x][1]代表锻炼
* dp[x][2]代表休息
*/
int[][] dp=new int[day+1][3];
for(int x=1;x {
//如果这一天可以工作,工作的话
if(work[x-1]==1)
{
dp[x][0]= Math.max(dp[x-1][1], dp[x-1][2])+1;
}
//如果这一天可以锻炼,锻炼的话
if(sport[x-1]==1)
{
dp[x][1]=Math.max(dp[x-1][0], dp[x-1][2])+1;
}
//休息一天
dp[x][2]=Math.max(dp[x-1][0], Math.max(dp[x-1][1], dp[x-1][2]));
}
System.out.println(day-Math.max(dp[day][0], Math.max(dp[day][1], dp[day][2])));
}
}


热文推荐
猜你喜欢
友情链接: 医学资料大全 农林牧渔 幼儿教育心得 小学教育 中学 高中 职业教育 成人教育 大学资料 求职职场 职场文档 总结汇报