地址

//这道题有点乱,故自己手打注释分清阶段 by CLaran 
#include <bits/stdc++.h>//要点 : 区间DP  环状    切成k份     最小最大值 
using namespace std;
int n,k,f[200][200][300],a[200],sum[300],ans;
int main(){
	cin >> n >> k;
	for(int i = 1;i <= n;i++){
		cin >> a[i];
		a[i+n] = a[i];
	}
	for(int i = 1;i <= 2*n;i++)
		sum[i] = a[i],sum[i] += sum[i-1];//前缀和预处理 
	//最小值部分
	memset(f,0x3f,sizeof(f));
	//预处理
	for(int i = 1;i <= 2*n;i++)
		for(int j = i;j <= 2*n;j++){
			if(i > j) continue;
		 	f[i][j][1] = sum[j]-sum[i-1];
			f[i][j][0] = sum[j]-sum[i-1];
			//预处理 
		}
	for(int l = 1;l <= k;l++)//切成k份 
		for(int len = 2;len <= n;len++)
			for(int i = 1;i+len-1 <= 2*n;i++){
				int j = i+len-1;
				for(int sl = 0;sl < l;sl++)
					for(int k = i;k < j;k++){
						int p1 = f[i][k][sl],p2 = f[k+1][j][l-sl-1];
						if(p1 < 0) p1 = 10-abs(p1)%10;
						else p1 %= 10;
						if(p2 < 0) p2 = 10-abs(p2)%10;
						else p2 %= 10;
						//以上是判断正负数求模 
						f[i][j][l] = min(f[i][j][l],p1*p2/*+sum[j]-sum[i-1]*/);
					}
			}
	ans = INT_MAX;
	for(int i = 1;i <= n;i++)
		ans = min(ans,f[i][i+n-1][k]);
	cout << ans << endl;
	//最大值部分 
	memset(f,0,sizeof(f));
	for(int i = 1;i <= 2*n;i++)
		for(int j = i;j <= 2*n;j++){
			if(i > j) continue;
			f[i][j][1] = sum[j]-sum[i-1];
			f[i][j][0] = sum[j]-sum[i-1];
			//预处理 
		} 
	for(int l = 1;l <= k;l++)//切成k份 
		for(int len = 2;len <= n;len++)
			for(int i = 1;i+len-1 <= 2*n;i++){
				int j = i+len-1;
				for(int sl = 0;sl < l;sl++)
					for(int k = i;k < j;k++){
						int p1 = f[i][k][sl],p2 = f[k+1][j][l-sl-1];
						if(p1 < 0) p1 = 10-abs(p1)%10;
						else p1 %= 10;
						if(p2 < 0) p2 = 10-abs(p2)%10;
						else p2 %= 10;
						//以上是判断正负数求模 
						f[i][j][l] = max(f[i][j][l],p1*p2/*+sum[j]-sum[i-1]*/);
					}
			}
	ans = 0;
	for(int i = 1;i <= n;i++)
		ans = max(ans,f[i][i+n-1][k]);
	cout << ans;
	return 0;
}