Ad-Advanced Selection

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

信息

ID
1366
难度
(无)
分类
其他 点击显示
标签
(无)
递交数
0
已通过
0
通过率
?
上传者