记录编号	166730	评测结果	AAAAA
题目名称	[NOIP 2003]数字游戏	最终得分	100
用户昵称	啊吧啦吧啦吧	是否通过	通过
代码语言	C++	运行时间	0.009 s
提交时间	2015-06-16 11:07:19	内存使用	1.11 MiB

#include<fstream>
#include<climits>

using namespace std;

const int MAXN = 51, MAXM = 10;
int dpa[MAXM][2*MAXN][2*MAXN]={0},dpi[MAXM][MAXN*2][MAXN*2]={0},num[MAXN*2],m,n;
ifstream fi("numgame.in");
ofstream fo("numgame.out");
#define cin fi
#define cout fo

main()
{
	int ansa = 0, ansi = INT_MAX;

//	ios::sync_with_stdio(false);
	cin >> n >> m;
	for(int i = 1; i <= n; i ++)
	{
		cin >> num[i];
		
		num[i + n] = num[i];
	}
	for(int i = 1; i <= 2 * n - 1; i ++)
		for(int j = i; j <= 2 * n - 1; j ++)
			dpa[1][i][j]=dpi[1][i][j]=((dpa[1][i][j-1]+num[j])%10+10)%10;
	for(int p = 2; p <= m; p ++)
		for(int i = 1; i <= n; i ++)
			for(int j = i; j <= 2 * n - 1; j ++)
				for(int k = i; k < j; k ++)
				{
				   dpa[p][i][j]=max(dpa[p][i][j],dpa[p-1][i][k]*dpa[1][k+1][j]);
				   if(dpi[p][i][j] == 0)
				   {
					   dpi[p][i][j] = dpi[p - 1][i][k] * dpi[1][k + 1][j];
					   continue;
				   }
				   dpi[p][i][j]=min(dpi[p][i][j],dpi[p-1][i][k]*dpi[1][k+1][j]);
				}
	for(int i = 1; i <= n; i ++)
	{
		ansa = max(ansa, dpa[m][i][i + n - 1]);
		ansi = min(ansi, dpi[m][i][i + n - 1]);
	}
	
	cout << ansi << endl << ansa;
}