NOIP2003普及组 数字游戏题解pascal

这是一道环形动态规划题目
可以把它拉成直线来做
f[i,j]表示前i个字符分成j组获得的最优值。
f[i,j]:=max(min)(f[k,j-1]+value(k+1,i));
代码如下
var
a,sum:array[0..101]of longint;
f:Array[1..100,1..100]of longint;
i,j,k,l,n,m,head,ans:longint;
procedure init;
var
i,j:longint;
begin
readln(n,m);
for i:=1 to n do
begin
readln(a[i]);
sum[i]:=sum[i-1]+a[i];
a[i+n]:=a[i];
end;
for i:=n+1 to 2*n do
sum[i]:=sum[i-1]+a[i];
a[2*n+1]:=a[1];
sum[2*n+1]:=sum[2*n]+a[1];
sum[0]:=0;
end;
function max(x,y:longint):longint;
begin
if x>y then exit(x) else exit(y);
end;
function min(x,y:longint):longint;
begin
if xend;
begin
init;
fillchar(f,sizeof(f),127);
ans:=maxlongint;
for head:=1 to n do
begin
for i:=head to head+n-1 do
f[i,1]:=(((sum[i]-sum[head-1])mod 10)+10)mod 10;
for i:=head+1 to head+n-1 do
for j:=2 to min(m,i-head+1) do
begin
for k:=(j+head-2) to i-1 do
if f[i,j]>f[k,j-1]*((((sum[i]-sum[k])mod 10)+10)mod 10) then
f[i,j]:=f[k,j-1]*((((sum[i]-sum[k])mod 10)+10)mod 10);
end;
if f[head+n-1,m] end;
writeln(ans);
for i:=1 to n do
for j:=1 to m do
f[i,j]:=-maxlongint;
ans:=-maxlongint;
for head:=1 to n do
begin
fillchar(f,sizeof(f),128);
for i:=head to head+n-1 do
f[i,1]:=(((sum[i]-sum[head-1])mod 10)+10)mod 10;
for i:=head+1 to head+n-1 do
for j:=2 to min(m,i-head+1) do
begin
for k:=(j+head-2) to i-1 do
if f[i,j] f[i,j]:=f[k,j-1]*((((sum[i]-sum[k])mod 10)+10)mod 10);
end;
if ans end;
writeln(ans);
end.