2003noip 数字游戏

　　这是一道环形动态规划题目
　　可以把它拉成直线来做
　　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 x　　end;
　　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.

通过所有测试数据
环形DP
program p2003_2(input,output);
const maxn=50;maxm=9;
type arr=array[0..maxn-1,1..maxn,0..2] of longint;
var n,m,t10,t:integer;
i,j,k:integer;
a:array[0..maxn-1] of integer;
min,max:arr;
m1,m2,temp:longint;
begin
assign(input,'game.in');
reset(input);
readln(n,m);
for i:=0 to n-1 do readln(a[i]);
close(input);
for i:=0 to n-1 do begin
temp:=0;
for j:=1 to n do begin
temp:=temp+a[(i+j-1) mod n];
if temp>=0 then t10:=temp mod 10
else t10:=(10-((-1)*temp) mod 10) mod 10;
min[i,j,0]:=t10;
max[i,j,0]:=t10;
min[i,j,1]:=t10;
max[i,j,1]:=t10;
end;
end;
for k:=1 to m-1 do begin

for j:=k+1 to n do
for i:=0 to n-1 do begin
m1:=2000000000;m2:=-2000000000;
for t:=k to j-1 do begin
if m1>min[i,t,1]*min[(i+t)mod n,j-t,0] then
begin m1:=min[i,t,1]*min[(i+t)mod n,j-t,0];
if m1<0 then writeln(m1,'=',min[i,t,1],'*',min[(i+t)mod n,j-t,0]);end;
if m2 begin m2:=max[i,t,1]*max[(i+t)mod n,j-t,0];
end;
end;
min[i,j,2]:=m1;
max[i,j,2]:=m2;
end;

for i:=0 to n-1 do
for j:=1 to n do begin
min[i,j,1]:=min[i,j,2];
max[i,j,1]:=max[i,j,2];
end;
end;

m1:=2000000000;m2:=-2000000000;
for i:=0 to n-1 do begin
if m1>min[i,n,1] then m1:=min[i,n,1];
if m2 end;
assign(output,'game.out');
rewrite(output);
writeln(m1);
writeln(m2);
close(output);
end.

program p2003_2(input,output);
const maxn=50;maxm=9;
type arr=array[0..maxn-1,1..maxn,0..2] of longint;
var n,m,t10,t:integer;
i,j,k:integer;
a:array[0..maxn-1] of integer;
min,max:arr;
m1,m2,temp:longint;
begin
assign(input,'game.in');
reset(input);
readln(n,m);
for i:=0 to n-1 do readln(a[i]);
close(input);
for i:=0 to n-1 do begin
temp:=0;
for j:=1 to n do begin
temp:=temp+a[(i+j-1) mod n];
if temp>=0 then t10:=temp mod 10
else t10:=(10-((-1)*temp) mod 10) mod 10;
min[i,j,0]:=t10;
max[i,j,0]:=t10;
min[i,j,1]:=t10;
max[i,j,1]:=t10;
end;
end;
for k:=1 to m-1 do begin

for j:=k+1 to n do
for i:=0 to n-1 do begin
m1:=2000000000;m2:=-2000000000;
for t:=k to j-1 do begin
if m1>min[i,t,1]*min[(i+t)mod n,j-t,0] then
begin m1:=min[i,t,1]*min[(i+t)mod n,j-t,0];
if m1<0 then writeln(m1,'=',min[i,t,1],'*',min[(i+t)mod n,j-t,0]);end;
if m2 begin m2:=max[i,t,1]*max[(i+t)mod n,j-t,0];
end;
end;
min[i,j,2]:=m1;
max[i,j,2]:=m2;
end;

for i:=0 to n-1 do
for j:=1 to n do begin
min[i,j,1]:=min[i,j,2];
max[i,j,1]:=max[i,j,2];
end;
end;

m1:=2000000000;m2:=-2000000000;
for i:=0 to n-1 do begin
if m1>min[i,n,1] then m1:=min[i,n,1];
if m2 end;
assign(output,'game.out');
rewrite(output);
writeln(m1);
writeln(m2);
close(output);
end.