记录编号	7081	评测结果	AAAAA
题目名称	[NOI 1996]添加号	最终得分	100
用户昵称	lc	是否通过	通过
代码语言	Pascal	运行时间	0.750 s
提交时间	2008-11-06 14:20:14	内存使用	10.40 MiB

program ex124;
 const
  maxn=200;  maxv=20;
 type
   ftype=array[0..60] of longint;
 var
     s:string;
     n,v:longint;
     a:array[1..maxn] of longint;
     f:array[1..maxn,0..maxv] of ftype;
     g:array[1..maxn,1..maxn] of ftype;

function minus(a:ftype; num:longint):ftype;
 var
     c:ftype;
     i:longint;

 begin
  fillchar(c,sizeof(c),0); c[0]:=a[0];
  for i:=1 to c[0] do c[i]:=a[i]*num;
  for i:=1 to c[0] do
    begin
     inc(c[i+1],c[i] div 10000);
     c[i]:=c[i] mod 10000
    end;
  while c[c[0]+1]>0 do
    begin
     inc(c[0]);
     inc(c[c[0]+1],c[c[0]] div 10000);
     c[c[0]]:=c[c[0]] mod 10000
    end;
  minus:=c;
 end;

function plus2(a:ftype; num:longint):ftype;
 var
     i:longint;

 begin
   a[1]:=a[1]+num;
   for i:=1 to a[0] do
     begin
      if a[i] div 10000=0 then break;
      inc(a[i+1],a[i] div 10000);
      a[i]:=a[i] mod 10000
     end;

   while a[a[0]+1]>0 do
    begin
     inc(a[0]);
     inc(a[a[0]+1],a[a[0]] div 10000);
     a[a[0]]:=a[a[0]] mod 10000;
    end;
  plus2:=a;
 end;



procedure ready;
 var
    i,j:longint;

 begin
  readln(s); n:=length(s);
  for i:=1 to n do a[i]:=ord(s[i])-48;
  readln(v);
  for i:=1 to n do begin g[i,1][0]:=1; g[i,1][1]:=a[i]; end;
   for j:=2 to n do
     for i:=1 to n-j+1 do
     g[i,j]:=plus2(minus(g[i,j-1],10),a[i+j-1]);
 end;

function plus(a,b:ftype):ftype;
 var
    i:longint;
    c:ftype;

 begin
  fillchar(c,sizeof(c),0);
  if a[0]>b[0] then c[0]:=a[0] else c[0]:=b[0];
  for i:=1 to a[0] do inc(c[i],a[i]);
  for i:=1 to b[0] do inc(c[i],b[i]);
  for i:=1 to c[0] do
   begin
    inc(c[i+1],c[i] div 10000);
    c[i]:=c[i] mod 10000
   end;
  while c[c[0]+1]>0 do
   begin
    inc(c[0]);
    inc(c[c[0]+1],c[c[0]] div 10000);
    c[c[0]]:=c[c[0]] mod 10000;
   end;

  plus:=c;
 end;


function small(a,b:ftype):boolean;
 var
    i:longint;

 begin
  if a[0]<b[0] then exit(true);
  if a[0]>b[0] then exit(false);
  for i:=a[0] downto 1 do
        if a[i]<b[i] then exit(true)
   else if a[i]>b[i] then exit(false);
  exit(false);
 end;


procedure main;
 var
    i,j,k:longint;
    tm:ftype;

 begin
  for i:=1 to n do f[i,0]:=g[1,i];

   for j:=1 to v do
    for i:=1 to n do
      begin
      f[i,j][0]:=maxlongint;
        for k:=j to i-1 do
           begin
            tm:=plus(f[k,j-1],g[k+1,i-k]);
             if small(tm,f[i,j])
             then f[i,j]:=tm;
           end;
      end;
 end;

procedure print;
 var
    i:longint;
 begin
  write(f[n,v,f[n,v,0]]);
  for i:=f[n,v,0]-1 downto 1 do
   begin
    if f[n,v,i]<10 then write(0);
    if f[n,v,i]<100 then write(0);
    if f[n,v,i]<1000 then write(0);
    write(f[n,v,i]);
   end;
  writeln;
 end;


begin
  assign(input,'exam4.in');
  assign(output,'exam4.out');
  reset(input); rewrite(output);
  ready;
  main;
  print;
  close(input); close(output);
end.