← 返回题目

题库练习打保龄球

← 上一题下一题 →

A346 | $打保龄球$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

有 $n$ 个球瓶等距排成一排，从左到右的编号分别为 $1,2,\cdots,n$。每个球瓶都有一个分值（可能为负数），第 $i$ 个球瓶的分值为 $a_{i}$。 给你 $K$ 个保龄球，每个球的直径为 $w$。也就是说，每个球可以击倒一个长度为 $w$ 的区间内的所有球瓶。当然，每个球只能投出一次。 每当用球击倒一个球瓶，他就会得到相应的分值,在某个球瓶被击倒后，球瓶原来的位置会留出空位。另外，球瓶 $1$ 的左边、球瓶$n$ 的右边都有足够的空位。 投出的保龄球可以经过空位，空位上原有的球瓶失效，即不会得到相应的分值。当然，保龄球可以不击倒任何球瓶。 想知道，你投完所有保龄球后，你最多可以得到多少分？

输入格式

共两行。 第一行3个正整数 $n,k,w$，分别表示球瓶数量、球的数量、球的直径。

输出格式

一行一个整数，表示能得到的最大的分值。 对于 $100\%$ 数据，$1\le n\le 10000,1\le k\le 500 , |ai|<=1000$

输入输出样例

输入 #1

9 3 3
2 8 -5 3 5 8 4 8 -6

输出 #1

C++ 编辑器

输入

输出