0309 pdd¶

只有四道编程算法题

1、多多在玩一个游戏，人物初始位于$x=0$位置，共有$n+1$张卡片可以使用，分别是：

• n张传送卡（数值为整数，可正可负）： $$ [a_1,a_2,\cdots,a_n] $$
  • 效果是：$x\to x+a_i$
• 以及一张翻转卡。
  • 效果是：$x\to -x$

n张传送卡片可以按照任意顺序使用，翻转卡可以在任何时候使用。

问：游戏结束时，多多最远能走多远？

2、和第一题同样的题设。

但是这次n张传送卡片只能按照1-n的顺序使用，翻转卡依旧可以在任何时候使用。

问：在游戏过程中，最远的一次能到哪里？

3、多多在看一本书。

可以一分钟看一页或者一分钟看两页。书本的每一页都有一定数量的知识： $$ book = [a_1,a_2,\cdots,a_n] $$ 如果一分钟看完一页，可以学到所有的知识。如果一分钟看完两页，只能学到两页知识之和的一半。

问：m分钟看完这本书，最多可以学到多少知识？如果看不完输出-1。

4、考虑一个有m行n列的剧院。

共有$mn$个观众。现在要根据身高顺序来安排座位，从左到右、从前到后身高依次递增。例如：

-> 1 1 2
-> 2 3 4
-> 6 7 7

然而观众抵达剧院的顺序是不固定的。假设按照下列顺序到达（$h_i$代表第i个到达观众的身高）： $$ h_1,h_2,\cdots,h_{mn} $$

观众只能从每一行的最左侧进入，在进入的过程中每经过一个已经有人的座位会增加1点拥挤度。

问：拥挤度最低是多少？