dp乱写3：环形区间dp（数字游戏）

状态：

fmax[i,j]//表示前i个数分成j个部分的最大值

fmin[i,j]//表示前i个数分成j个部分的最小值

边界:fmax[i,1]:=(sum[i] mod 10+10) mod 10（sum[i]为前i个数的总和）;fmin[i,1]:=(sum[i] mod 10+10) mod 10;

状态转移方程:

fmax[i,j]:=max(fmax[i,j],fmax[k,j-1]*ff(sum[i]-sum[k]));

fmin[i,j]:=min(fmin[i,j],fmin[k,j-1]*ff(sum[i]-sum[k]){ff为取sum[i]-sum[k]对10取余的结果});//找一个中间点，把1到k分j-1个部分，而之前我们已经做出了决策，答案保存在f[k,j-1]里，另外k+1到i看成一部分，利用前缀和求出从k+1到i的值。

处理环：把环看成一条链，旋转出这条环所有的可能性（旋转即把整个数组里的数都往前1格，第一个数则到最后一个位置）

uses math;

var  a,sum:array[..]of longint;

     fmax,fmin:array[..,..]of longint;

     n,m,i,j,k,x,maxn,minn,t:longint;

function ff(x:longint):longint;

begin

 exit(((x mod )+) mod );

end;

procedure dp;

var i,j,k:longint;

begin

 for i:= to n do sum[i]:=sum[i-]+a[i];

 for i:= to n do

  for j:= to m do begin

  fmax[i,j]:=-maxlongint div ;

  fmin[i,j]:=maxlongint div ;

 end;

 for i:= to n do begin

  fmax[i,]:=ff(sum[i]);

  fmin[i,]:=ff(sum[i]);

 end;

 for i:= to n do

  for j:= to m do

   for k:=j- to i- do begin

    fmax[i,j]:=max(fmax[i,j],fmax[k,j-]*ff(sum[i]-sum[k]));

    fmin[i,j]:=min(fmin[i,j],fmin[k,j-]*ff(sum[i]-sum[k]))

   end;

  maxn:=max(maxn,fmax[n,m]);

  minn:=min(minn,fmin[n,m]);

end;

begin

 readln(n,m);

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

 minn:=maxlongint;

 for i:= to n do begin

  t:=a[];

  for j:= to n- do  a[j]:=a[j+];

  a[n]:=t;

  dp;

 end;

 writeln(minn);

 writeln(maxn);

end.