题解 P5124 【[USACO18DEC]Teamwork】

题解 P5124 【[USACO18DEC]Teamwork】

这题居然没有p的题解，那我来水一发

感觉这题不到蓝吧

题目描述：长度为n的序列，可以把一段长为k的连续序列改成最大值

不难想到dp

用b[i]表示前i个数能达到的最大价值。 b[i]:=max(b[j]+(i-j)*max(a[j]),b[i]) 而b[i]所能达到的最小值为b[i-1]+a[i],所以可以提前处理b[i]， 但i-j可能会<=0,怎么办呢？特判一下呗

代码

uses math;//math库是个好东西
var
n,m,i,j,k,maxx:longint;
a,b:array[0..100005] of longint;//不管怎么说，开大点总不会错
begin
readln(n,m);
for i:=1 to n do read(a[i]);
for i:=1 to n do
begin
maxx:=a[i];
b[i]:=b[i-1]+a[i];
for j:=1 to m-1 do
begin
if i<=j then break;//如果i<=j,那就跳过循环
maxx:=max(maxx,a[i-j]);
b[i]:=max(b[i-j-1]+maxx*(j+1),b[i]);//dp转移方程
end;
end;
writeln(b[n]); //输出最大价值b[n]
end.