haihongyuan.com
海量文库 文档专家
全站搜索:
您现在的位置:首页 > 初中教育 > 学科竞赛学科竞赛

数字游戏的解题报告

发布时间:2013-12-18 12:31:34  

分析:

对于这题先处理圈,我们先把圈转换成线形的数组。例如,样例转换成线形数组后有下列4种形态:

4 3 –1 2

3 –1 2 4

-1 2 4 3

2 4 3 –1

然后考虑最终的状态,这就是n个数被分成m份,要产生这个状态,一定是前j个数被分成m-1份 * 后n-j个数的和的模。

由此可得出动态转移方程:F[I,k]=max{F[j,k-1]*后I-j个数的和的摸}

从而得出程序:

for k:=2 to m do

for i:=1 to n do

begin

f [ I , k ]:= -maxlongint;

for j:=k-1 to i-1 do

begin

L:=sum(j+1 , i);

L:=L mod 10;

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

if f [ j , k-1 ] * L > f [ I , k ] then f [ I , k ] := f [ j , k-1 ] * L end;

end;

程序如下:

var

f :array[0..50,0..9] of longint;

I ,j ,k ,l ,n ,m ,max ,t : longint;

a : array[1..50] of longint;

function sum( j , I : longint) : longint;

var

p,g:longint;

begin

g:=0;

for p:=j to i do

g:=g+a[p];

sum:=g;

end;

begin

readln(n,m);

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

max:=-maxlongint;

for t:=1 to n do {化环为链,穷举“第一刀”的位置}

begin

fillchar(f,sizeof(f),0);

for i:=1 to n do { F [ I , 1 ]为前I个数的和的模,边界} begin

for j:=1 to i do f[i,1]:=f[i,1]+a[j]; {求出前I个数的和}

f[i,1]:=f[i,1] mod 10; {取模}

if f[i,1]<0 then f[i,1]:=f[i,1]+10; {按题意取模} end;

for k:=2 to m do {枚举份数}

for i:=k to n do {枚举待划分数的个数}

begin

f[i,k]:=-maxlongint;

for j:=k to i do {枚举第k份的开始位置} begin

L:=sum(j,i); {求第k份数的和的模} L:=L mod 10;

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

if f[j-1,k-1]*L>f[i,k] then f[i,k]:=f[j-1,k-1]*L end;

end;

if f[n,m]>max then max:=f[n,m]; {打擂台}

{为穷举下一种情况作准备}

k:=a[1];

for i:=2 to n do a[i-1]:=a[i];

a[n]:=k;

end;

writeln(max);

end.

上一篇:算法分析
下一篇:题二: 选数
网站首页网站地图 站长统计
All rights reserved Powered by 海文库
copyright ©right 2010-2011。
文档资料库内容来自网络,如有侵犯请联系客服。zhit326@126.com