P5171: 数字游戏 -训练套题T7T3
传统题
1.000s
时间限制
128MB
内存限制
3 提交
3 解决
【题目描述】
3. 数字游戏(game.pas)
【问题描述】
在你面前有一圈整数（一共n个），你要按顺序将其分为m个部分，将各个部分内的数字相加，所得的m个结果对10取特殊模后再相乘，最终得到一个整数K。游戏的要求是使你所得的K值最大或者最小。
我们约定的特殊模为smod:
当x为正数时， x smod 10=x mod 10
当x为负数时， x smod 10 =x mod 10 +10
例如当n=4，m=2，这4个数分别是4，3，2，-1
最小值（（2-1）smod
10）*（（4+3）smod 10）=1*7=7
最大值（（2+4+3）smod
10）*（-1
smod 10）=9*9=81
【输入文件】
文件第一行有两个整数，n（1<=n<=50）和m（1<=m<=9）。
以下n行每行有1个整数，其绝对值不超过10^4,按顺序给出圈中的数字，首尾相接。
【输出文件】
文件有两行，各包含一个非负整数。第一行是最小值，第二行是最大值。
【样例输入1】
4 2
4
3
-1
2
【样例输出1】
7
81
【输入样例2】
5 3
158
-265
-404
-75
281
【输出样例2】
3
120
【提示】
HJF:
Dp，将环形通过枚举断点变成链式结构，设f[i,j,k]表示从第i个数到第j个数分成k个部分的最优值，A[i]表示前i个数之和。