记录编号	5756	评测结果	AAAAA
题目名称	[NOI 1996]添加号	最终得分	100
用户昵称	elysian	是否通过	通过
代码语言	Pascal	运行时间	2.405 s
提交时间	2008-10-28 15:24:27	内存使用	1.15 MiB

program elysian;   
const  
fin='exam4.in';fout='exam4.out';   
  
var  
f1,f2:text;   
s:string;   
a,b:array[1..200] of longint;   
f:array[0..201,0..20] of string;   
n,m,ad:longint;   
ff:string;   
  
procedure init;   
var  
i,j,k:longint;   
tmp:string;   
begin  
assign(f1,fin);reset(f1);   
readln(f1,s);   
read(f1,m);   
close(f1);   
n:=length(s);   
end;   
  
  
procedure gaojing(x,y:string);   
var  
l1,l2:longint;   
i,j,k:longint;   
tmp:string;   
  
BEGIN   
l1:=length(x);l2:=length(y);   
if l1>l2 then j:=l1 else j:=l2;   
for i:=1 to 200 do a[i]:=0;   
for i:=1 to 200 do b[i]:=0;   
  
k:=0;   
for i:=l1 downto 1 do begin  inc(k);a[k]:=ord(x[i])-48;end;   
k:=0;   
for i:=l2 downto 1 do begin inc(k);b[k]:=ord(y[i])-48;end;   
  
for i:=1 to j do  
begin  
a[i]:=a[i]+b[i];   
if a[i]>=10 then begin  a[i]:=a[i]-10;inc(a[i+1]);end;   
end;   
  
if a[j]=10 then a[j]:=1;   
if a[j+1]=0 then j:=j-1;   
k:=0;   
  
  
ff:='';   
for i:=j+1 downto 1 do  
begin  
inc(k);   
str(a[i],tmp);   
insert(tmp,ff,k);   
end;   
  
  
END;   
  
  
procedure bj(i,j:longint);   
begin  
if length(ff)<length(f[i,j]) then f[i,j]:=ff   
else if (length(ff)=length(f[i,j]))and(ff<f[i,j]) then f[i,j]:=ff;   
  
end;   
  
procedure dp;   
var  
i,j,p:longint;   
BEGIN   
  
  
for i:=1 to n do f[i,1]:=copy(s,1,i);   
  
for j:=2 to m+1 do  
for i:=j to n do  
for p:=j-1 to i-1 do  
begin  
if ( length(f[p,j-1]) <= ( i div 2 +1) ) and (length(copy(s,p+1,i-p))<=(i div 2 +1))then  
begin  
gaojing(f[p,j-1],copy(s,p+1,i-p));   
if f[i,j]='' then f[i,j]:=ff   
else  bj(i,j);   
end;   
end;   
END;   
  
  
  
begin  
init;   
dp;   
assign(f2,fout);rewrite(f2);   
writeln(f2,f[n,m+1]);   
close(f2);   
end.