/ OIer TK / 题库 /

Selection

Selection

测试数据来自 system/1202

背景

wind发明了一个好玩的游戏,叫小杉一起玩。

但小杉玩了十几盘,总是输,他想知道是不是从一开始他就注定要输。

描述

这个游戏是这样的,wind先写下一排数。既然是一排,当然有首尾咯。

wind和小杉每次只能从这排数的头或尾取一个数。

最后谁取的数的和多,谁就赢了。

假如你是小杉,请算出你最多能取到的和。

wind的智商是很高的(怪不得小杉一直输),你必须知道他总是做出最优决策。

格式

输入格式

每组测试数据的
第一行仅有一个数n(n<=2000)
第二行也仅有一个数,0表示wind先取数,1表示小杉先取数
第三行有n个数,是wind给出的一排数。这n个数均不超过1e6

输出格式

对每组测试数据输出一行
仅有一个整数s
表示小杉最多能取到多少数

样例1

样例输入1

1
1
1

样例输出1

1

限制

每个测试点1s

提示

如果您AC此题
那么...................................................................您就AC了此题

来源

UVAOJ
lolanv改编

信息

ID
1193
难度
9
分类
动态规划 点击显示
标签
(无)
递交数
1
已通过
1
通过率
100%
上传者