【小奇模拟赛】小奇的糖果2

2016年5月21日7050

【题目背景】

小奇不小心让糖果散落到了地上,但是提比已经在来小奇家的路上了,小奇没有足够的时间把糖果都藏起来。

【问题描述】

有n个糖果排成一排,相邻糖果的距离为一个单位长度,编号为1-n,每个糖果的价值为wi,起始时小奇的爪子在第start个糖果,每个单位时间它有两种选择,捡起当前位置的糖果(显然每个糖果只能捡起来一次),把爪子向左或右移动一个单位长度。

它想知道在m个单位时间内能捡起的最大糖果价值和。

【输入格式】

第一行包括3个整数,n,start,m。

第二行n个数,第i个数字表示wi。

【输出格式】

输出一个整数表示答案。

【样例输入】

5 2 7

10 2 20 30 1

【样例输出】

60

【数据范围】

对于 10% 的数据, n ≤ 10;

对于 40% 的数据, n ≤ 500;

另有 20% 的数据, start = 1;

对于 100% 的数据, n ≤ 100000, m ≤ 250000, 0 < wi <= 10^9。

本题来自ioi2014 holiday

题解和代码略。。。