自动搬运

查看原文

来自洛谷，原作者为

	徐振羽 **

搬运于2025-08-24 21:20:15，当前版本为作者最后更新于2019-09-28 10:45:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一看到这道题，我感觉是个深搜

但我们看一数据大量，也就循环个5000亿次而已，于是果断放弃

我们决定用DP，不要问为什么，因为我们可以从几个已知数据得出未知数据

这里要注意了，因为题目中数字构成一个环，所以我们要先化环为链

我们看看我们怎样DP，我们需要一个三维数组f[i][j][l]，i和j表示我们取第i个数字到第j个数字，l表示我们将第i个数字到第j个数字分为l段（f存最大值）

我们明白了动态规划中数组的含义，就能较容易的推出动态规划转移方程了

我们用一个4重循环，第1,2重i,j表示第i个数字到第j个数字，l表示我们将第i个数字到第j个数字分为l段，k表示我们在i,j中取得中间值，将第i个数字到第j个数字拆成第i个数字到第k个数字和第k+1个数字到第j个数字。

明白了动态规划中数组的含义和动态规划转移方程，我们只需要进行一个初始化就行了，通过动态规划转移方程，我们发现无法推出f[i][j][1]，所以我们要做的就是在动归开始前，将全部f[i][j][1]赋值

至于f[i][j][1]的初始值怎么赋，就是枚举i,j，再将第i个数字到第j个数字全部加起 mod 10 就行了

代码附上

#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; 
}