记录编号	379123	评测结果	AAAAA
题目名称	[NOIP 2003]数字游戏	最终得分	100
用户昵称	rewine	是否通过	通过
代码语言	C++	运行时间	0.037 s
提交时间	2017-03-05 19:29:49	内存使用	1.93 MiB

#include <cstdio>
#include <queue>
#include <iostream>
#include <cstring>

using namespace std;
typedef long long LL;

inline void read(LL &x) {
    char c;bool flag = 0;
    while((c=getchar())<'0'||c>'9') flag |= (c=='-');
    x=c-'0';while((c=getchar())>='0'&&c<='9') x = x*10+c-'0';
    flag?x=-x:x;
}

LL g[103][103][10],f[103][103][10],a[103];

int main() {
    freopen("numgame.in","r",stdin);freopen("numgame.out","w",stdout);
	LL n,m; read(n); read(m);
	for (int i = 1; i <= n; i++) read(a[i]);
	memset(g,127/3,sizeof(g));
	for (int i = n+1; i <= n+n; i++) a[i] = a[i-n];
	int t = n*2;
	for (int i = 1; i <= t; i++)
	 for (int j = i; j <= t; j++) {
	   f[i][j][1] = ((f[i][j-1][1]+a[j])%10+10)%10;
	   g[i][j][1] = f[i][j][1];
	}
	for (int k = 2; k <= m; k++)
	  for (int i = 1; i <= t; i++)
	   for (int j = i; j <= t; j++)
		 for (int c = i+k-2; c < j; c++)
		 g[i][j][k] = min(g[i][j][k],g[i][c][k-1]*g[c+1][j][1]);
	for (int k = 2; k <= m; k++)
	  for (int i = 1; i <= t; i++)
	   for (int j = i; j <= t; j++)
		 for (int c = i+k-2; c < j; c++)
		 f[i][j][k] = max(f[i][j][k],f[i][c][k-1]*f[c+1][j][1]);
	LL mx = 0,mi = ~0u>>1;
	for(int i = 1; i <= n; i++)
	 mx = max(mx,f[i][i+n-1][m]),mi = min(mi,g[i][i+n-1][m]);
	cout << mi << "\n" << mx;
    return 0;
}