P1880 [NOI1995] 石子合并

//石子合并是道有环的动态规划题，而对于环来说，最简单有效的方式就是暴力断环，但这样的话4层循环n^4时间复杂度，很明显会超时，所以我们把数组开大两倍，当做把环里面所有的可能都拆出来，去枚举，n^3复杂度，不会超时 
//f[i][j]表示从i到j所花费的体力最小值 ，dp[i][j]表示从i到j所花费的体力最大值 
#include <iostream>
#include <cstring>

using namespace std;

const int N = 100 * 2 + 5;//数组开两倍，用来存环带来的特殊情况 

int a[N],n,s[N],f[N][N],dp[N][N];//s用来存前缀和，f数组用来存最小值，dp数组用来存最大值 

int main(){
	
	memset (f,0x3f3f3f3f,sizeof(f));//记得初始化，不然最小值是0 
	
	cin >> n;
	
	for (int i = 1;i <= n;i ++){
		
		cin >> a[i];
		s[i] = s[i - 1] + a[i];//前缀和基本公式 
	}
	for (int i = n + 1;i <= n * 2;i ++){//初始化一下后面的n 
		
		a[i] = a[i - n];
		s[i] = s[i - 1] + a[i];//也要有前缀和 
	}
	
	for (int i = 1;i <= n * 2;i ++){//注意要小于等于n*2，因为这两倍空间都需要初始化 
		
		f[i][i] = 0;//表示现在这堆石子不移动，所以不需要消耗体力 
		dp[i][i] = 0;
		
	}
	
	for (int len = 2;len <= n;len ++){//这层循环枚举区间长度 
		for (int l = 1;l <= n * 2 - len + 1;l ++){//这层枚举左端点，n*2-len+1是最后一个左端点的位置，如果超过，就越界了 
			
			int r = l + len - 1;//知道了长度和左端点，右端点也就知道啦 
			
			for (int k = l;k < r;k ++){//在区间中找出一个k,使得左端点到k的所花费的体力加右端点到k所花费的体力最小 
				
				f[l][r] = min (f[l][r],f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);//找最小的，注意要加前缀和，因为最后剩下的两堆石子还要合并 
				dp[l][r] = max (dp[l][r],dp[l][k] + dp[k + 1][r] + s[r] - s[l - 1]);
				
			}
			
		}
	}
	int minn = 0x3f3f3f3f,maxx = 0;//附个初值，好取大小 
	for (int i = 1;i <= n;i ++){
		
		minn = min (minn,f[i][i + n - 1]);//表示从i开始，长度为n的区间中所耗费体力最小的那个 
		maxx = max (maxx,dp[i][i + n - 1]);//表示从i开始，长度为n的区间中所耗费体力最大的那个  
		
	}
	cout << minn << '\n' << maxx;//最后输出答案 
	return 0;//华丽结束 
}