洛谷p1043

#include<iostream>
using namespace std;
long long a[1001],x[1001],n,m,max1,min1=1000000000000000;
//x为一开始读入的数据，a为便于计算一段之和的前缀和 
long long f[101][101][11],f1[101][101][11]; 
//f数组存最大值，f1数组存最小值 
int main(){
	cin>>n>>m;
	for (int i=1;i<=100;i++)
		for (int j=1;j<=100;j++)
			for (int k=1;k<=10;k++)
				f1[i][j][k]=10000000000;
	//先给f1数组赋上巨大的值，便于计算之和的最小值 
	for (int i=1;i<=n;i++)
	{
		cin>>x[i];//读入 
		a[i]+=a[i-1]+x[i];//前缀和 
	}
	//化环为链 
	for (int i=n+1;i<=n*2;i++) a[i]+=a[i-1]+x[i-n];//前缀和 
	for (int i=1;i<=n*2;i++)
		for (int j=1;j<=n*2;j++)
		{
			f[i][j][1]=(a[j]-a[i-1]+100000000000)%10;//前缀和求一段数的和 
			f1[i][j][1]=(a[j]-a[i-1]+100000000000)%10;//前缀和求一段数的和 
			//因为输入有负数，所以a[j]可能会小于a[i-1],所以我们给他加上巨大值 
		}
	//赋初始值	
	for (int i=1;i<=n*2;i++)//枚举开始的数字位置 
	{
		for (int j=i+1;j<=n*2;j++)//枚举结束的数字位置 
		{
			for (int l=2;l<=m;l++)//枚举分段的数量 
			{
				for (int k=i;k<j;k++)//枚举中间数的位置 
				{
					f[i][j][l]=max(f[i][j][l],f[i][k][l-1]*f[k+1][j][1]);//动态规划转移方程
					f1[i][j][l]=min(f1[i][j][l],f1[i][k][l-1]*f1[k+1][j][1]);//动态规划转移方程 
				}
			}
		}
	}
	for (int i=1;i<=n;i++) 
	{
		max1=max(max1,f[i][i+n-1][m]);//求一段的最大值 
		min1=min(min1,f1[i][i+n-1][m]);//求一段的最小值  
	}
	cout<<min1<<endl<<max1<<endl;//输出
	return 0; 
}