[UER #7] 短路

Description

“第七套广播体操,原地踏步——走!”

众所周知,跳蚤们最喜欢每天早起做早操,经常天还没亮就齐刷刷地站在操场做着反复纵跳热热身。跳晚国在研制三星 note7 的时候注意到了这点,于是他们打算让炸弹更快地引爆,这样就可以消灭更多早起的跳蚤。

三星 note7 的主板可以看作是由 (2n+1)×(2n+1)个中继器构成的,某些中继器会有导线连在一起,左上角和右下角的中继器分别连着电源的正负极。

电流流过一根导线的时间可忽略不计,但当电流经过中继器时,会延缓一段时间再从中继器流出。这个时间只跟该中继器本身有关,我们把这段时间的长度称为中继器的延时值。

这些中继器由导线连接围成一个一个的层,同个层的中继器的种类都一样,而不同层的种类都不一样,可以发现总共有 n+1 层。当 n=4时,主板大概长这样:

图1

跳晚们打算再加几根导线将某些中继器连接起来.凭借发达的重工业,他们能生产出无数条导线。但由于主板的限制,他们的导线只能和主板四周的边平行,且其长度只够连接相邻两个中继器。

现在他们想知道,他们改造的三星 note7 的电源正极流出的电流能在多短的时间到达电源负极从而造成短路,这样电池就会释放出巨大的能量摧毁跳蚤国的有生力量了。

请参考输入格式和样例配图来更好地理解题意。

限制与约定

测试点编号 n
1 N<5
2 N<2000
3
4 N<5000
5
6 N<100000
7
8
9
10

对于所有数据,保证每个数都是不超过1e9的正整数。

时间限制:1s

空间限制:256M


Solution

首先,假设当前正在第i层的左上角【从外到内数】,那么我们只可能有两种决策

  1. 直接从外侧绕到这层的右下角
  2. 进入下一层

那么这层应该走几步再进入下一层呢?

我们发现,出于最小化目标值的目的,我们肯定尽量少走那些代价大的中转器。于是我们在非前缀最小值的中转器上至多走一次,这样也就是把所有前缀最小值存入一个数组里,每次在前者走的距离即为两层之差。

出题人真是太厉害啦!QQ图片20160623113002

 

发表评论