XX大学的金字塔

Time Limit
1s
Memory Limit
131072KB
Judge Program
Standard
Ratio(Solve/Submit)
6.67%(2/30)
Description:

众所周知,在很久以前, XX 大学3号教学楼的地下有一个神奇的金字塔,这是很久以前有智慧的巨龙们的杰作。如图,金字塔的顶层只有一个房间,每向下一层便多一个房间,房间的位置还展示了住在里面的巨龙们之间的主仆关系:住在某房间的巨龙,是住在这个房间正下方两个房间巨龙的主人。即,住在第i层第j号位置的巨龙,是住在第i+1层第j号和第j+1号位置巨龙的主人。

作为巨龙,他们当然十分热爱珠宝,而作为生活在中华大地上的巨龙,他们还有一套严格的等级进贡体制:每个房间的巨龙会收到其两个仆人价值分别为x和y的的贡品,而这个巨龙还需要向他的主人进贡进价值为max(x, y)的贡品,同时,这个值也代表着这条龙的开心度。特别的,住在金字塔顶端的巨龙不需要向任何龙进贡;驻守在金字塔边缘两列的巨龙只需要向自己唯一的主人进贡。
现已知住在金字塔顶第n层每个巨龙的开心度,求住在金字塔第n层及以上每条巨龙的开心度之和

Input:

输入包含多组测试数据,第一行为一个正整数 T (1  T 10) 表示有 T 组测试数据。
测试数据第一行包含一个正整数 n (1 106);
第二行包含 n 个非负整数,ai 依次表示住在第 n 层第 i 条巨龙的开心度

Output:

对于每组测试数据,
输出一行包含一个非负整数 Ans 表示问题答案。

Sample Input:
2
4
3 1 2 4
5
2 3 1 4 2
Sample Output:
30
49
Source:

Davones


Submit