haihongyuan.com

# 数字游戏的解题报告

4 3 –1 2

3 –1 2 4

-1 2 4 3

2 4 3 –1

for k:=2 to m do

for i:=1 to n do

begin

f [ I , k ]:= -maxlongint;

for j:=k-1 to i-1 do

begin

L:=sum(j+1 , i);

L:=L mod 10;

if L<0 then L:=L+10;

if f [ j , k-1 ] * L > f [ I , k ] then f [ I , k ] := f [ j , k-1 ] * L end;

end;

var

f :array[0..50,0..9] of longint;

I ,j ,k ,l ,n ,m ,max ,t : longint;

a : array[1..50] of longint;

function sum( j , I : longint) : longint;

var

p,g:longint;

begin

g:=0;

for p:=j to i do

g:=g+a[p];

sum:=g;

end;

begin

for i:=1 to n do read(a[i]);

max:=-maxlongint;

for t:=1 to n do {化环为链，穷举“第一刀”的位置}

begin

fillchar(f,sizeof(f),0);

for i:=1 to n do { F [ I , 1 ]为前I个数的和的模，边界} begin

for j:=1 to i do f[i,1]:=f[i,1]+a[j]; {求出前I个数的和}

f[i,1]:=f[i,1] mod 10; {取模}

if f[i,1]<0 then f[i,1]:=f[i,1]+10; {按题意取模} end;

for k:=2 to m do {枚举份数}

for i:=k to n do {枚举待划分数的个数}

begin

f[i,k]:=-maxlongint;

for j:=k to i do {枚举第k份的开始位置} begin

L:=sum(j,i); {求第k份数的和的模} L:=L mod 10;

if L<0 then L:=L+10;

if f[j-1,k-1]*L>f[i,k] then f[i,k]:=f[j-1,k-1]*L end;

end;

if f[n,m]>max then max:=f[n,m]; {打擂台}

{为穷举下一种情况作准备}

k:=a[1];

for i:=2 to n do a[i-1]:=a[i];

a[n]:=k;

end;

writeln(max);

end.