Ad-Advanced Selection
测试数据来自 system/1254
背景
wind发明了一个好玩的游戏,叫全班同学一起玩。(p1202,p1207)
但小杉玩了十几盘,总是输,终于被大家给踢了出来……
如今小杉要翻身了,他自己把这个游戏改了一点规则,要挑战wind。
描述
这个游戏是这样的,小杉先写下一排数。既然是一排,当然有首尾咯。
小杉和wind轮流取数(小杉先),每个人每次只能从这排数的头两个或尾两个取一个数。
最后谁取的数的和多,谁就赢了。
wind的智商是很高的(怪不得小杉一直输),你必须知道他总是做出最优决策。
小杉想知道他最多能取到多少和。
格式
输入格式
每组测试数据的
第一行有一个数n(5<n<=60)
第二行有n个数,是小杉给出的一排数。这n个数均不超过1e6
输出格式
对每组测试数据输出两行
第一行输出小杉最多取到多少和
第二行输出小杉做的决策,取最左边的两个数输出L1,L2,取最右边的两个数输出R1,R2,决策间用一个空格隔开,行末有一个空格
当小杉面临决策时只剩下五个数或以下了,你就可以不输出决策了
样例1
样例输入1
8
1 2 3 4 5 6 7 8
样例输出1
20
R2 R2
限制
每个测试点1s
来源
lolanv