Question

pascal数字游戏的简便做法

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

Answer 1

对于这题给人的第一感觉就是用穷举法，把每个情况都探到即可解题。但你要仔细看一下题目要求就会发现问题所在。题目要求n（1≤n≤50）和m（1≤m≤9）粗略估计一下所可能出现的情况应为429即是4.06×1014次。这样是无法在规定的时间里完成。那么如何解决呢？答案就是用递推法。如何递推呢？我们假设有n个数分成m个部分，也可以看成切m个口。第一个切口切完后，我们就可以看成一个有n个数组成的长链。那末这第一刀就有n个切法 ,我们就先对第一种切法进行研究，也就是把从1到n个数切m-1刀分成m个部分。首先我们想象第一部分可分为1个数字、2个数字、3个数字……（n-m）个数字。我们把其求和取模的结果分别存入数组的（n-m）个单元中。接着我们可以把第一、二部分合并考虑了，我们可以认为只有（n-m+1）个数字分成两个部分和（n-m）个数字分成两个部分……和2个数字分成两个部分的（n-m）种情况。见下图所示，两个部分寻找最大值过程,我们再把每种情况中的最大值和最小值找出，分别存入d和x两个数组中。再接着我们可以把第一、二、三部分合并考虑了，我们可以认为只有（n-m+2）个数字分成三个部分和（n-m+1）个数字分成三个部分……和3个数字分成三个部分的（n-m）种情况。我们再把每种情况中的第三部分，分别于两个部分的最大值和最小值相乘就可以找到三个部分的最大值和最小值。如下图所示，三个部分寻找最大值过程。

下面就是我所编的参考程序：

Var

a,b:Array[1..100]Of integer;

d,x:Array[1..50]Of longint;

m,n,l,i,j:Integer;

mk,sk:longint;

Procedure Work;

Var

i,j,s,k,k1:Integer;

da,xiao:longint;

Begin

for i:=1 to l do

begin

s:=0;

for j:=1 to l-i+1 do

begin

s:=s+b[m+j+i-2];

end;

d[i]:=s mod 10;

if d[i]<0 then d[i]:=d[i]+10;

end;

x:=d;

for i:=m-1 downto 1 do

begin

for j:=1 to l do

begin

da:=0;xiao:=90000000;

for k:=j to l do

begin

s:=0;

for k1:=j to k do

s:=s+b[i+k1-1];

s:=s mod 10;

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

if da<s*d[k] then da:=s*d[k];

if xiao>s*x[k] then xiao:=s*x[k];

end;

d[j]:=da;x[j]:=xiao;

end;

end;

end;

begin

readln(n,m);

mk:=0;sk:=90000000;l:=n-m+1;

for i:=1 to n do

readln(a[i]);

for i:=1 to n-1 do

a[i+n]:=a[i];

for i:=1 to n do

begin

for j:=1 to n do
b[j]:=a[i+j-1];
Work;
if mk<d[1] then mk:=d[1];
if sk>x[1] then sk:=x[1];
end;
writeln(sk);writeln(mk);
end.