「小奇模拟赛」小奇的糖果2

2016年5月21日3,4640

「题目背景」

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

「问题描述」

有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

题解和代码略。。。

avatar
  Subscribe  
提醒