记录编号	32001	评测结果	AAAAAAAAAA
题目名称	技能树	最终得分	100
用户昵称	lizhe	是否通过	通过
代码语言	Pascal	运行时间	0.121 s
提交时间	2011-11-04 16:40:14	内存使用	10.69 MiB

program skill;
var
  i,j,k,n,m,max:longint;
  f:array[0..51,0..51,0..500]of int64;
  g:array[0..50,0..500]of int64;
  sum,a:array[0..50,0..50]of int64;
procedure init;
begin
  assign(input,'skill.in');
  reset(input);
  assign(output,'skill.out');
  rewrite(output);
  read(n,m);
  for i:=1 to n do
    for j:=1 to n-i+1 do
	  read(a[i,j]);
  for i:=1 to n do
    for j:=1 to n do
      sum[i,j]:=sum[i-1,j]+a[i,j]
end;

procedure dp;
begin
  for j:=1 to n do
  begin
    for k:=1 to m do
      g[j,k]:=g[j-1,k];
    for i:=1 to n do
      for k:=1 to m do
      begin
        if k-1>0 then
          if f[i,j,k]<f[i-1,j,k-1]+a[i,j] then
            f[i,j,k]:=f[i-1,j,k-1]+a[i,j];
        if k-i>0 then
          if f[i,j,k]<f[i+1,j-1,k-i]+sum[i,j] then
            f[i,j,k]:=f[i+1,j-1,k-i]+sum[i,j];
        if i=1 then
        begin
          if f[1,j,k]<g[j-1,k-1]+a[1,j] then
            f[1,j,k]:=g[j-1,k-1]+a[1,j];
          if g[j,k]<f[1,j,k] then
            g[j,k]:=f[1,j,k]
        end
      end
  end
end;

procedure print;
begin
  for j:=1 to n do
    if max<f[1,j,m] then
      max:=f[1,j,m];
  writeln(max);
  close(input);
  close(output)
end;

 begin
  init;
  dp;
  print
end.