问题 5100 --数字游戏-NOIP2003PJT2

5100: 数字游戏-NOIP2003PJT2

时间限制: 1 Sec  内存限制: 128 MB
提交: 53  解决: 24
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][44kb]

题目描述

数字游戏

(game.pas/c/cpp)

题目描述

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

例如,对于下面这圈数字(n=4m=2):

当要求最小值时,((2-1) mod 10)×((4+3) mod 10)=1×7=7,要求最大值时,为((2+4+3) mod 10)×(-1 mod 10)=9×9=81。特别值得注意的是,无论是负数还是正数,对10取模的结果均为非负值。

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

输入格式

输入文件第一行有两个整数,n1n50)和m1m9)。以下n行每行有个整数,其绝对值不大于104,按顺序给出圈中的数字,首尾相接。

输出

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

样例输入

4 2
4
3
-1
2

样例输出

7
81

输入

输出

提示


1.算法:动态规划




对于将已经纳入计算的i个数分成j份,其最大值(或最小值)表示为maxnum[i][j](minnum[i][j]),枚举循环变量K表示纳入计算i-k个数分成j-1份时其最大值(或最小值)maxnum[i-k][j-1](minnum[i-k][j-1]),因此动态方程应当为:



Maxnum[i][j]=max(Maxnum[i-k][j-1]*sum[i-k+1][i],Maxnum[i][j]);



Minnum[i][j]=max(Minnum[i-k][j-1]*sum[i-k+1][i],Minnum[i][j]);



其中sum[i-k+1]代表从i-k+1i的和。




2.细节:



   (1)环到链的转换:



       方法1,每次DP时枚举断点,可行但不理想,



       方法2,读入时直接将数组增加一倍,方便,但最后答案要注意,推荐用此方法。



                    for i:=1 to n do       begin   readln(a[i]); a[i+n]:=a[i];      end;



  (2)mod的处理,在pascal中被除数是负数,则mod的结果为负数,故此处要做转换。



       如: a mod 10=(a+100000000) mod 10







来源

[提交][状态]