/ Vijos / 题库 /

笨笨的道路通行

笨笨的道路通行

背景

笨笨:“又这么多车……”
路人甲:“你先过吧……”
笨笨:“不会撞上吧?……”
路人甲:“谁知道呢……”

描述

在笨笨上学的路上,必定要经过一条宽宽的马路……
马路上有很多条道:快车道、慢车道、超车道、大型车道……每条道占一个单位宽度,每隔一段时间就会有一辆车从道上通过。

现在,笨笨要过的马路宽n个单位长度(和宽度同为一个单位)。

笨笨过马路每个单位时间只有3种动作:前进,止步,后退。

为了确定是否应该为了不迟到直接瞬移到马路对面,笨笨想找你确认一下最少需要多少时间才能通过马路。

格式

输入格式

输入第一行一个数test(1<=test<=100),表示该测试点测试数据组数。

每组测试数据格式如下:
第一行为一个数n(0<=n<=1000),表示这条路的宽度。

接下来一行为n个数,从出发点向终点,ai(1<=ai<=1000)表示第i条道每ai时间通过一辆车。

输出格式

对于每组数据:
若能够通过马路,输出一个数,即最少过马路所需时间。

若不能通过马路,输出一句话:You can't cross the road!

样例1

样例输入1

1
3
2 4 3

样例输出1

5

样例2

样例输入2

1
1
1

样例输出2

You can't cross the road!

限制

1s

提示

【对于样例1的解释】
{0表示笨笨,-表示没有车,|表示有车,B表示起点,E表示终点}
时刻0:0|||E 开始
时刻1:B0--E 前进
时刻2:B|0-E 前进
时刻3:B-0|E 止步
时刻4:B||0E 前进
时刻5:B---0 抵达

【对于样例2的解释】
时刻0:0|E
时刻1:0|E
时刻2:0|E
时刻3:0|E
……
所以笨笨是无法通过的……只好动用瞬移技能了……

来源

图片

信息

ID
1651
难度
8
分类
动态规划 点击显示
标签
递交数
878
已通过
134
通过率
15%
被复制
2
上传者

相关

在下列训练计划中:

RP++分类题库

在下列比赛中:

笨笨工作室告别十月模拟赛