← 返回目录

算法笔试模拟题精解之“寒假活动”

第 27 / 74 卷日期：

算法笔试模拟题精解之“寒假活动”

贡献者 | 汪丹辉

简介：本题充分利用四个开门状态，就可以使用动态规划。

题目描述

等级：中等

知识点：DP

查看题目：寒假活动

小森马上就要迎来自己长达 n 天的寒假了，为不让自己无聊，他决定寒假每天都

尽量出去运动。小森最喜欢的运动是滑雪和游泳。

但是并不是每天滑雪馆和游泳馆都开门，我们定义 a[i] 表示第 i 天的开门状态：

  1. a[i] = 0, 滑雪馆和游泳馆都不开门。
  2. a[i] = 1, 滑雪馆开门，但是游泳馆不开门。
  3. a[i] = 2, 滑雪馆不开门，但是游泳馆开门。
  4. a[i] = 3, 滑雪馆和游泳馆都开门。

但是小森又是一个讨厌重复的人，因此他不会连着两天做同样的运动，但是可以

连续两天都不运动。

也就是说，只有当滑雪馆开门并且前一天他没有去滑雪的时候他才能去滑雪。游

泳同理。因为运动是非常累的，所以小森每天最多只能做一种运动。

现在小森已经得到了寒假时候滑雪馆和游泳馆的开门安排，即数组 a，他现在想

输入假期天数 n1 <= n <= 100000，和包含 n 个数字的数组 a，表示场馆开门

安排。

输出一个数字，表示不运动的最小值天数。

示例 1

输入：

5

[3,3,1,2,0]

输出：

1

注意：

小森的最优策略是第一天滑雪，第二天游泳，第三天滑雪，第四天游泳，第五天

不运动。

题解思路：动态规划

本题充分利用四个开门状态，就可以使用动态规划：

小森只有 3 种可能的状态 ( 不运动、滑雪、游泳 )。本题要求不运动的最小值天

数，可以反向思维，求运动的最大天数，然后用总天数减去最大运动天数即为最小运

动天数

dpi 表示第 i 天，选择休息（j=0）、游泳（j=1）、滑雪（j=2）时的最大运动天数

状态转移方程为

dpi = max(dpi-1, dpi-1, dpi-1)

如果游泳馆开门

dpi = max(dpi-1+1, dpi-1+1)

否则

dpi = max(dpi-1, dpi-1, dpi-1)

如果滑雪馆开门

dpi = max(dpi-1+1, dpi-1+1)

否则

dpi = max(dpi-1, dpi-1, dpi-1)

遍历天数，完成上面状态转移，就完成了动态规划的过程。

第一天的起始值也需要判断开门情况

这里需要指出 dpi 只是表示第 i 天滑雪时的最大运动，而不是第 i 天一定会滑雪

时间复杂度：O(n)

空间复杂度：O(kn)

是不是有思路了呢，点击链接立刻答题：>> 寒假活动

全站分卷索引 · 74 卷
  1. 1一、算法思想
  2. 2算法笔试模拟题精解之“打怪兽”
  3. 31.2 贪心
  4. 4算法笔试模拟题精解之“最强的团队”
  5. 5算法笔试模拟题精解之“Tom 爱吃巧克力”
  6. 6算法笔试模拟题精解之“吃奶酪”
  7. 7算法笔试模拟题精解之“一的个数”
  8. 8算法笔试模拟题精解之“Bob 的花束”
  9. 9算法笔试模拟题精解之“钱庄”
  10. 10算法笔试模拟题精解之“移动射击”
  11. 11算法笔试模拟题精解之“相似数组”
  12. 12算法笔试模拟题精解之“过吊桥”
  13. 13算法笔试模拟题精解之“完美排列”
  14. 14算法笔试模拟题精解之“采摘圣诞果”
  15. 15算法比赛模拟题精解之“Tairitsu and Dynamic Objects”
  16. 16算法笔试模拟题精解之“Codancer 的炸弹引爆”
  17. 17算法笔试模拟题精解之“学习小组”
  18. 18算法笔试模拟题精解之“恢复字符串”
  19. 191.3 DP/ 动态规划
  20. 20算法笔试模拟题精解之“寻找等比数列”
  21. 21算法笔试模拟题精解之“字符配对”
  22. 22算法笔试模拟题精解之“数组染色”
  23. 23算法笔试模拟题精解之“连绵的群山”
  24. 24算法笔试模拟题精解之“难住Tom 的问题”
  25. 25算法笔试模拟题精解之“变化的字符”
  26. 26算法笔试模拟题精解之“跳房子”
  27. 27算法笔试模拟题精解之“寒假活动”
  28. 28算法笔试模拟题精解之“最短路”
  29. 29算法笔试模拟题精解之“codancer 上楼”
  30. 30算法笔试模拟题精解之“木棒拼接”
  31. 31算法笔试模拟题精解之“Codancer 的数组封印”
  32. 32算法笔试模拟题精解之“Jerry 的异或运算”
  33. 33算法笔试模拟题精解之“小明的数学作业”
  34. 34算法笔试模拟题精解之“奇偶数列”
  35. 351.4 剪枝
  36. 361.5 尺取法
  37. 37算法笔试模拟题精解之“调整数组”
  38. 38算法笔试模拟题精解之“最优分组”
  39. 39算法笔试模拟题精解之“破译密码”
  40. 40二、数据结构
  41. 412.2 搜索
  42. 42算法笔试模拟题精解之“能量半径”
  43. 43算法笔试模拟题精解之“苹果收获程序”
  44. 44算法笔试模拟题精解之“恐怖的辐射”
  45. 45算法笔试模拟题精解之“树的拆分”
  46. 46算法笔试模拟题精解之“Password”
  47. 47算法笔试模拟题精解之“神奇数字在哪里”
  48. 48算法笔试模拟题精解之“神奇的棋子”
  49. 492.3 树
  50. 50算法笔试模拟题精解之“Codancer 的旅行”
  51. 51算法笔试模拟题精解之“Codancer 的求和”
  52. 52算法笔试模拟题精解之“找出二叉搜索树的第2 大的数”
  53. 532.4 线型
  54. 54算法笔试模拟题精解之“最活跃的数”
  55. 55算法笔试模拟题精解之“非递减序列”
  56. 56算法笔试模拟题精解之“Tom 跳方格”
  57. 57算法笔试模拟题精解之“复杂的字符串”
  58. 58算法笔试模拟题精解之“神秘消失”
  59. 59三、计算
  60. 60算法笔试模拟题精解之“简单题？
  61. 61算法笔试模拟题精解之“朋友一生一起走”
  62. 62算法笔试模拟题精解之“正三角塔”
  63. 63算法笔试模拟题精解之“组队难题”
  64. 64算法笔试模拟题精解之“2n 合体”
  65. 65算法笔试模拟题精解之“平行线”
  66. 66算法笔试模拟题精解之“叠叠高”
  67. 67算法笔试模拟题精解之“公平”
  68. 68算法笔试模拟题精解之“Tom 的手工课”
  69. 69算法笔试模拟题精解之“填数问题”
  70. 70算法笔试模拟题精解之“Jerry 的考验”
  71. 71算法笔试模拟题精解之“超车”
  72. 72算法笔试模拟题精解之“坏掉的时钟”
  73. 73算法笔试模拟题精解之“期末考试”
  74. 74算法笔试模拟题精解之“滑雪比赛”