记搜代码

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int fmax[205][205], fmin[205][205], qzh[205];
int dp1(int l, int r)
{
	if (fmax[l][r])
		return fmax[l][r];
	for (int i = l; i < r; i++)
		fmax[l][r] = max(fmax[l][r], dp1(l, i) + dp1(i + 1, r) + qzh[r] - qzh[l - 1]);
	return fmax[l][r];
}
int dp2(int l, int r)
{
	if (fmin[l][r] != 0x3f3f3f3f)
		return fmin[l][r];
	for (int i = l; i < r; i++)
		fmin[l][r] = min(fmin[l][r], dp2(l, i) + dp2(i + 1, r) + qzh[r] - qzh[l - 1]);
	return fmin[l][r];
}
int main()
{
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &qzh[i]);
		qzh[i] += qzh[i - 1];
	}
	for (int i = n + 1; i <= 2 * n; i++)
		qzh[i] = qzh[n] + qzh[i - n];
	memset(fmin, 0x3f, sizeof fmin);
	dp1(1, n * 2);
	dp2(1, n * 2);
	int amax = 0, amin = 0x3f3f3f3f;
	for (int i = 1; i <= n; i++)
	{
		amax = max(amax, fmax[i][n + i - 1]);
		amin = min(amin, fmin[i][n + i - 1]);
	}
	printf("%d\n%d", amin, amax);
	return 0;
}