program exx;
var i,j,m,n,k,max,x,y,min:longint;
a:array[1..100] of longint;
f,f1:array[1..100,1..100,1..9] of longint;
begin
readln(n,k);
for i:=1 to n*2 do
begin
readln(a[i]);
a[n+i]:=a[i];
end;
for x:=2 to k-1 do
for i:=1 to 2*n do
for j:=1 to 2*n do
f1[i,j,x]:=10000;
for i:=1 to n do
for j:=i to n+i-1 do
for x:=1 to j-i+1 do
begin
f[i,j,1]:=f[i,j,1]+a[i+x-1];
f[i,j,1]:=(f[i,j,1]+10000) mod 10;
f1[i,j,1]:=f[i,j,1];
end;
for i:=n+1 to 2*n do
for j:=i to 2*n do
begin
f1[i,j,1]:=f1[i-n,j-n,1];
f[i,j,1]:=f1[i,j,1];
end;
for x:=2 to k do
for i:=1 to n do
for j:=i+1 to n+i-1 do
for y:=i to j-1 do
begin
if f[i,y,x-1]*f[y+1,j,1]>f[i,j,x] then
f[i,j,x]:=f[i,y,x-1]*f[y+1,j,1];
if f1[i,y,x-1]*f1[y+1,j,1]<f1[i,j,x] then
f1[i,j,x]:=f1[i,y,x-1]*f1[y+1,j,1];
end;
max:=0; min:=maxlongint;
for i:=1 to n do
begin
if f[i,i+n-1,k]>max then max:=f[i,i+n-1,k];
if f1[i,i+n-1,k]<min then min:=f1[i,i+n-1,k];
end;
writeln(min);
writeln(max);
end.
很丑的程序…………
不过ac了 庆祝一下~
var n,m,i:integer;
a:array[1..100] of integer;
ma,mi,f1,f2:longint;
function max(x,y:longint):longint;
begin if x>y then max:=x else max:=y; end;
function min(x,y:longint):longint;
begin if x<y then min:=x else min:=y; end;
function mm(x:longint):longint;
var y:longint;
begin
if x>=0 then mm:=x mod 10
else begin
y:=x;
while y<0 do inc(y,10);
mm:=y mod 10;
end;
end;
function dp1(l,r:integer):longint;
var w:array[1..50] of integer;
i,j,k,n:integer;
h:array[0..50,0..50] of longint;
f:array[0..50,0..8] of longint;
begin
n:=r-l+1; fillchar(f,sizeof(f),0);
fillchar(h,sizeof(h),0);
for i:=l to r do w[i-l+1]:=a[i];
for i:=1 to n do for j:=i to n do h[i,j]:=h[i,j-1]+w[j];
for i:=1 to n do f[i,0]:=mm(h[i,n]);
for i:=n downto 1 do
for k:=1 to m do
for j:=i to n-k do
f[i,k]:=max(f[i,k],mm(h[i,j])*f[j+1,k-1]);
dp1:=f[1,m];
end;
function dp2(l,r:integer):longint;
var w:array[1..50] of integer;
i,j,k,n:integer;
h:array[0..50,0..50] of longint;
ha:array[0..50,0..8] of integer;
kk:longint;
f:array[0..50,0..8] of longint;
begin
n:=r-l+1; fillchar(f,sizeof(f),0);
fillchar(h,sizeof(h),0); fillchar(ha,sizeof(ha),0);
for i:=l to r do w[i-l+1]:=a[i];
for i:=1 to n do for j:=i to n do h[i,j]:=h[i,j-1]+w[j];
for i:=1 to n do f[i,0]:=mm(h[i,n]);
for i:=n downto 1 do
for k:=1 to m do
for j:=i to n-k do begin
kk:=mm(h[i,j])*f[j+1,k-1];
if (ha[i,k]=ha[j+1,k-1]+1)and(f[i,k]>kk) then
f[i,k]:=kk
else if ha[i,k]<ha[j+1,k-1]+1 then begin
f[i,k]:=kk;
ha[i,k]:=ha[j+1,k-1]+1;
end;
end;
dp2:=f[1,m];
end;
begin
readln(n,m); mi:=200000000; dec(m);
for i:=1 to n do begin readln(a[i]); a[i+n]:=a[i]; end;
for i:=1 to n do begin
f1:=dp1(i,i+n-1);
f2:=dp2(i,i+n-1);
ma:=max(ma,f1); mi:=min(mi,f2);
end;
writeln(mi);
writeln(ma);
end.
自认为比较清楚