记录编号	246890	评测结果	AAAAA
题目名称	[NOIP 2003]数字游戏	最终得分	100
用户昵称	zys	是否通过	通过
代码语言	C++	运行时间	0.018 s
提交时间	2016-04-07 16:08:20	内存使用	2.03 MiB

#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))

#include<cstdio>
#include<cstring>

using namespace std;

int n,m,a[120];
int MAX=-0x7fffffff,MIN=0x7fffffff;
int h[120][120];
int f[120][120][20];
int F[120][120][20];
//从i到j分为k个部分相加所得结果

void DP()
{
	for(int l=2;l<=n;l++)
	    for(int i=1;i<=2*n-l;i++){
			int j=i+l-1;
			h[i][j]=h[i][j-1]+a[j];
			F[i][j][1]=f[i][j][1]=((h[i][j]%10)+10)%10;
	    }
	for(int l=2;l<=n;l++)
	    for(int i=1;i<=2*n-l;i++){
			int j=i+l-1;
			for(int k=2;k<=(l<m ? l:m);k++){
				f[i][j][k]=6000000;
				for(int d=i+k-2;d<j;d++){
					F[i][j][k]=Max(F[i][j][k],F[i][d][k-1]*F[d+1][j][1]);
					f[i][j][k]=Min(f[i][j][k],f[i][d][k-1]*f[d+1][j][1]);
				}
			}
	    }
	for(int i=1;i<=n;i++){
		MAX=Max(MAX,F[i][i+n-1][m]);
		MIN=Min(MIN,f[i][i+n-1][m]);
	}

}
int main()
{
    freopen("numgame.in","r",stdin);
	freopen("numgame.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
	    scanf("%d",&a[i]);
	    a[n+i]=a[i];
	    h[i][i]=h[n+i][n+i]=a[i];
	    F[i][i][1]=F[n+i][n+i][1]=f[i][i][1]=f[n+i][n+i][1]=(a[i]%10);
	    if(a[i]<0)
	    {
		    F[i][i][1]+=10;
		    F[n+i][n+i][1]=f[i][i][1]=f[n+i][n+i][1]=F[i][i][1];
	    }
    }
    DP();
	printf("%d\n%d",MIN,MAX);
}