原題來自:USACO 2011 Open Gold
在一年前贏得了小鎮(zhèn)的最佳草坪比賽后,F(xiàn)J 變得很懶,再也沒有修剪過草坪?,F(xiàn)在,新一輪的最佳草坪比賽又開始了,F(xiàn)J 希望能夠再次奪冠。
然而,F(xiàn)J 的草坪非常臟亂,因此,F(xiàn)J 只能夠讓他的奶牛來完成這項(xiàng)工作。FJ 有 $N$ 只排成一排的奶牛,編號(hào)為 $1$ 到 $N$。每只奶牛的效率是不同的,奶牛 $i$ 的效率為 $E_i$ 。
靠近的奶牛們很熟悉,如果 FJ 安排超過 $K$ 只連續(xù)的奶牛,那么這些奶牛就會(huì)罷工去開派對(duì)。因此,現(xiàn)在 FJ 需要你的幫助,計(jì)算 FJ 可以得到的最大效率,并且該方案中沒有連續(xù)的超過 $K$ 只奶牛。
第一行:空格隔開的兩個(gè)整數(shù) $N$ 和 $K$;
第二到 $N+1$ 行:第 $i+1$ 行有一個(gè)整數(shù) $E_i$ 。
一行一個(gè)值,表示 FJ 可以得到的最大的效率值。
5 2 1 2 3 4 5
12
樣例說明:
FJ 有 $5$ 只奶牛,他們的效率為 $1,2,3,4,5$。他們希望選取效率總和最大的奶牛,但是他不能選取超過 $2$ 只連續(xù)的奶牛。FJ 選擇出了第三只以外的其他奶牛,總的效率為 $1+2+4+5=12$。
數(shù)據(jù)范圍與提示:
對(duì)于全部數(shù)據(jù),$1≤N≤10^5 ,0≤E_i≤10^9$ 。