求救啊..10W火急 [复制链接]

2003NOIP的第二題.<數字遊戲>....大家可以用搜索幫我做一下麽..超時肯定的..但是沒關系...我只是想看看程序...謝謝了啊...很急啊

【问题描述】丁丁最近沉迷于一个数字游戏之中。这个游戏看似简单，但丁丁在研究了许多天之后却发觉原来在简单的规则下想要赢得这个游戏并不那么容易。游戏是这样的，在你面前有一圈整数（一共n个），你要按顺序将其分为m个部分，各部分内的数字相加，相加所得的m个结果对10取模后再相乘，最终得到一个数k。游戏的要求是使你所得的k最大或者最小。

例如，对于下面这圈数字（n=4，m=2）：
2
4 - 1
  3
当要求最小值时，((2-1) mod 10)×((4+3) mod 10)=1×7=7，要求最大值时，为((2+4+3) mod 10)×(-1 mod 10)=9×9=81。特别值得注意的是，无论是负数还是正数，对10取模的结果均为非负值。

丁丁请你编写程序帮他赢得这个游戏。

【输入格式】输入文件第一行有两个整数，n（1≤n≤50）和m（1≤m≤9）。以下n行每行有个整数，其绝对值不大于104，按顺序给出圈中的数字，首尾相接。

【输出格式】输出文件有两行，各包含一个非负整数。第一行是你程序得到的最小值，第二行是最大值。


【输入样例】
4 2
4
3
-1
2

【输出样例】
7
81

用动规
矩阵保留状态

楼上正解。
to lz，ms没有人会为这一题写一个搜索程序的吧。

Const Maxn=50;
      Maxm=9;
Var h:array[1..Maxn] of Integer;
    g:array[1..Maxn,1..Maxn] of LongInt;
    Fmin,Fmax:array[1..Maxn,1..Maxm] Of Longint;
    n,m,i,j,k,l:Integer;
    Max,Min,Tmax,Tmin,s:Longint;
    fi,fo:String;
Procedure readfile;
Begin
  Write(''Input File Name: ''); Readln(fi);
  Write(''Output FIle Name:''); Readln(fo);
  Assign(Input,fi); Assign(Output,fo);
  Reset(Input);  Rewrite(Output);
  Readln(n,m);
  For i:=1 to n do
  Readln(h);
  Close(Input);
End;
Procedure init;
Begin
  For i:=1 to n do
  For j:=i to n do
    Begin
    s:=0;
    For k:=i to j do s:=s+h[k];
    s:=s mod 10;
    If s<0 Then s:=10+s;
    g[i,j]:=s;
    End;
  For i:=1 to n do
  For j:=1 to m do
    Begin Fmin[i,j]:=1;  Fmax[i,j]:=1 End;
  For i:=1 to n do
    Begin
    Fmin[i,1]:=g[1,i];  Fmax[i,1]:=g[1,i]
    End
End;
Procedure move;
Var temp,p:Integer;
Begin
  temp:=h[1];
  For p:=1 to n-1 do
    h[p]:=h[p+1];
  h[n]:=temp;
End;
Procedure solute;
Begin
Max:=-Maxint; Min:=Maxint;
For l:=1 to n do
Begin
  Init;
  For i:=2 to n do
  For j:=2 to m do
    Begin
    Tmax:=-Maxint;
    Tmin:=Maxint;
    For k:=j-1 to i-1 do
      Begin
        If TMax<Fmax[k,j-1]*g[k+1,i] Then Tmax:=Fmax[k,j-1]*g[k+1,i];
        If TMin>Fmin[k,j-1]*g[k+1,i] Then Tmin:=Fmin[k,j-1]*g[k+1,i];
      End;
    Fmax[i,j]:=Tmax; Fmin[i,j]:=Tmin;
    End;
    If Max<Fmax[n,m] Then Max:=Fmax[n,m];
    If Min>Fmin[n,m] Then Min:=Fmin[n,m];
    move;
  End;
End;
　

Procedure Print;
Begin
Writeln(Min);
Writeln(Max);
close(output);
End;
Begin
  Readfile;
  Solute;
  Print
End.