1778 - 数字游戏
时间限制 : 1 秒
内存限制 : 128 MB
丁丁最近沉迷于一个数字游戏之中。这个游戏看似简单，但丁丁在研究了许多天之后却发觉原来在简单的规则下想要赢得这个游戏并不那么容易。游戏是这样的，在你面前有一圈整数（一共n个），你要按顺序将其分为m个部分，各部分内的数字相加，相加所得的m个结果对10取模后再相乘，最终得到一个数k。游戏的要求是使你所得的k最大或者最小。
例如，对于下面这圈数字（n=4，m=2）：
<!--[if gte mso 9]>Normal07.8 磅02falsefalsefalseMicrosoftInternetExplorer4<![endif]--><!--[if gte mso 9]><![endif]--><!--[if gte mso 10]>
<![endif]-->
当要求最小值时，<span>((2-1) mod 10)</span>×<span>((4+3) mod 10)=1</span>×<span>7=7</span>，要求最大值时，为<span>((2+4+3) mod 10)</span>×<span>(-1 mod 10)=9</span>×<span>9=81</span>。特别值得注意的是，无论是负数还是正数，对<span>10</span>取模的结果均为非负值。
题目输入
输入文件第一行有两个整数，n（1≤n≤50）和m（1≤m≤9）。以下n行每行有个整数，其绝对值不大于104，按顺序给出圈中的数字，首尾相接。
题目输出
输出文件有两行，各包含一个非负整数。第一行是你程序得到的最小值，第二行是最大值。
输入/输出样例
输入格式
4 2 4 3 -1 2
输出格式
7 81
C++解答
#include <stdio.h> #include <string.h> #define MAX 10000000 #define MIN -10000000 int line[200],n,m,Min,Max,sum[200]; int f[200][20];//f[i][j]=第1-i个数分成j份，结果最大值 int g[200][20];//g[i][j]=第1-i个数分成j份，结果最小值 int min(int a,int b) { if(a>b) return b; return a; } int max(int a,int b) { if(a>b) return a; return b; } void dp(int a[]) { int i,j,k; for(i=1;i<=n;i++) sum[i]=sum[i-1]+a[i]; for(i=0;i<=n;i++) for(j=0;j<=m;j++) { f[i][j]=0; g[i][j]=-1u>>1; } for(i=1;i<=n;i++) { f[i][1]=g[i][1]=(sum[i]%10+10)%10; } f[0][0]=1; g[0][0]=1; for(j=2;j<=m;j++) { for(i=j;i<=n;i++) { for(k=j-1;k<i;k++) { { f[i][j]=max(f[i][j],f[k][j-1]*(((sum[i]-sum[k])%10+10)%10)); g[i][j]=min(g[i][j],g[k][j-1]*(((sum[i]-sum[k])%10+10)%10)); } } } } Max=max(Max,f[n][m]); Min=min(Min,g[n][m]); } int main() { int i,j,k; Max=0; Min=-1u>>1; scanf("%d%d",&n,&m); for(i=1;i<=n;i++) { scanf("%d",&line[i]); line[i+n]=line[i]; } for(i=0;i<n;i++) dp(line+i); printf("%d\n%d\n",Min,Max); return 0; }