记录编号	323796	评测结果	AAAAA
题目名称	[NOIP 2003]数字游戏	最终得分	100
用户昵称	Hzoi_chairman	是否通过	通过
代码语言	C++	运行时间	0.007 s
提交时间	2016-10-17 07:29:37	内存使用	0.37 MiB

/*
	Name: 数字游戏
	Copyright: 
	Author: chairman
	Date: 17/10/16 07:26
	Description: f[i][j]表示前i个分成j部分所得最优值，f[i][j]=min(f[i][j],f[k][j-1]*(s[i]-s[k]))，求最大值同理，枚举起点即可 
				 注意初始化时也需取模成正的，因为计算时是一部分， 
*/
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
int read()
{
	int x,f=1;
	char ch;
	while(ch=getchar(),!isdigit(ch))if(ch=='-')f=-1;
	x=ch-48;
	while(ch=getchar(),isdigit(ch))x=x*10+ch-48;
	return x*f;
}
void write(int x)
{
	if(x<0)putchar('-'),x=-x;
	int cnt=0;char ch[50];
	while(ch[++cnt]=x%10+48,x/=10);
	while(putchar(ch[cnt]),--cnt);
	putchar('\n');
}
int f[120][120],s[120],a[120];
int main()
{
	freopen("numgame.in","r",stdin);
	freopen("numgame.out","w",stdout);
	int n=read(),m=read(),ans=0x7f7f7f7f;
	for(int i=1;i<=n;i++)a[i]=a[i+n]=read();
	for(int i=1;i<=2*n;i++)s[i]=s[i-1]+a[i];
	for(int i=1;i<=2*n;i++)f[i][i]=a[i];
	for(int p=1;p<=n;p++)
	{
		memset(f,0x7f,sizeof f);
		for(int i=p;i<=n+p-1;i++)f[i][0]=1,f[i][1]=((s[i]-s[p-1])%10+10)%10;
		for(int i=p;i<=n+p-1;i++)
			for(int j=2;j<=min(m,i);j++)
				for(int k=j-1+p;k<i;k++)
					f[i][j]=min(f[i][j],f[k][j-1]*(((s[i]-s[k])%10+10)%10));
		ans=min(ans,f[n+p-1][m]);
	}
	write(ans);
	ans=0;
	for(int p=1;p<=n;p++)
	{
		memset(f,0,sizeof f);
		for(int i=p;i<=n+p-1;i++)f[i][0]=1,f[i][1]=((s[i]-s[p-1])%10+10)%10;
		for(int i=p;i<=n+p-1;i++)
			for(int j=2;j<=min(m,i);j++)
				for(int k=j-1+p;k<i;k++)
					f[i][j]=max(f[i][j],f[k][j-1]*(((s[i]-s[k])%10+10)%10));
		ans=max(ans,f[n+p-1][m]);
	}
	write(ans);
//	system("pause");
}