第三题：保龄球（提高组第二试2011年10月22日）（2011年NOIP冲刺模拟试题）
保龄球
【问题描述】
你一个人保龄球馆去打保龄球。总共有k个球可用。每个球的宽度为w。在你前方有n个球棒要打。这n球棒紧密的排成一行，且第i个球棒宽度为1，价值为xi。你的每个球恰能击中第a个~第a+w-1个的球棒（如果此球棒存在的话）。球棒被打到就倒了，且互不影响。你可以向任意方向击球，甚至球的一部分可以越过最左、最右边球棒所构成的边界。求最大价值。
【输入】
文件第一行是三个整数n,k,w。以下n行是n个整数，第i个代表xi。
【输出】
输出文件仅一行，为最大价值。
【样例输入输出】
| bowling.in | bowling.out |
9 2 3 2 8 5 1 9 6 9 3 2 | 39 |
【数据范围】
对于40%的数据，满足1≤n,w,k≤100；
对于100%的数据，满足1≤n≤10000，1≤w≤100，1≤k≤500；
解题思路：
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！