Ruican @ 2016-06-10 17:58:31
var(这是没改过会输出路径的版本,请忽视路径部分)
a,sp,k:array[0..200000]of longint;
i,j,tem1,tem2,l,r,n,mid:longint;
procedure print(x:longint);
begin
if sp[x]>-1 then print(sp[x]);
write(x,' ');
end;
begin
readln(n,l,r);
for i:=1 to n+1 do
read(a[i-1]);
sp[0]:=-1;
for i:=1 to l-1 do
k[i]:=-10000000;
if (2*l-1)<r then
mid:=2*l-1
else mid:=r;
for i:=l to mid do
begin
k[i]:=a[i];
sp[i]:=0;
end;
for i:=mid+1 to n do
begin
if (i=mid+1)or(tem2=(i-r-1)) then
begin
tem1:=-maxlongint;
for j:=i-r to i-l do
if k[j]>tem1 then
begin
tem1:=k[j];
tem2:=j;
end;
k[i]:=tem1+a[i];
sp[i]:=tem2;
end else
begin
if k[i-l]>tem1 then
begin
tem1:=k[i-l];
tem2:=i-l;
end;
k[i]:=tem1+a[i];
sp[i]:=tem2;
end;
end;
tem1:=-10000000;
for i:=n+1-r to n do
if k[i]>tem1 then
begin
tem1:=k[i];
tem2:=i;
end;
writeln(tem1);
print(tem2);
write(-1);
end.
by 姚文涛 @ 2016-06-11 14:34:00
有可能洛谷的数据坑人
by zhaimingshuzms @ 2016-07-12 18:49:54
我也是额
by zhaimingshuzms @ 2016-07-12 19:22:40
216 改不好
by Ruican @ 2016-07-25 16:34:20
可同学的单调队列就能过
by CKnight @ 2017-06-22 15:15:43
看看名字颜色
by Alex_Wei @ 2019-09-03 22:36:44
by tallsky @ 2020-07-28 11:07:54
考古
by u822844 @ 2023-08-06 16:00:04
5的次幂系列
第3站:
by long_long__int @ 2023-08-09 11:20:23
5的次幂系列
第3站:
by WuMin4 @ 2024-08-08 16:52:21
烤股