석자 합병 문제는 세 가지로 나뉜다.

1. 임의로 병합 2. 인접한 것은 병합되고 직선으로 배열 3. 인접한 것은 병합되고 동그라미로 둘러싸인다

1. 욕심만 부리면 해결

과일 합치기(욕심 문제)

2. 직선형

합병석자 직선형은 구간 dp문제에 대해 구간으로 세분화해야 한다. 우리는 dp수 그룹 dp[i][j]의 의미를 이렇게 정의할 수 있다. i번째 돌을 합병해서 j번째 돌의 최소(최대) 득점을 얻는 것이다. 그럼 찾아보자.

int findMin(int l, int r)
{
	if(dp[l][r])
	return dp[l][r];
	if(l == r)
	return 0;
	int _min = MAX;//0x3f3f3f3f
	int s = 0;
	for(int i = l; i <= r; i++)
	s += a[i];//    ，       
	for(int i = l; i < r; i++)
	_min = min(_min, findMin(l, i) + findMin(i+1, r) + s);//     
	dp[l][r] = _min;
	return dp[l][r];
}

s의 의미는 l에서 r 구간에 있는 모든 돌의 합을 찾는 것이다. 마지막 두 무더기를 합친 AC 코드에 사용한다.

#include
#include
#include
using namespace std;
int n;
int dp[107][107];
int a[107];
const int MAX = 0x3f3f3f3f;

int findMin(int l, int r)
{
	if(dp[l][r])
	return dp[l][r];
	if(l == r)
	return 0;
	int _min = MAX;
	int s = 0;
	for(int i = l; i <= r; i++)
	s += a[i];//    ，       
	for(int i = l; i < r; i++)
	_min = min(_min, findMin(l, i) + findMin(i+1, r) + s);
	dp[l][r] = _min;
	return dp[l][r];
}

int findMax(int l, int r)
{
	if(dp[l][r])
	return dp[l][r];
	if(l == r)
	return 0;
	int _max = -1;
	int s = 0; 
	for(int i = l; i <= r; i++)
	s += a[i];//    ，       
	for(int i = l; i < r; i++)
	_max = max(_max, findMax(l, i) + findMax(i+1, r) + s);
	dp[l][r] = _max;
	return dp[l][r];
}
int main()
{
	while(scanf("%d", &n) != EOF)
	{
		memset(dp,0,sizeof(dp));
		for(int i = 1; i <= n; i++)
			cin >> a[i];
		cout << findMin(1,n) << " ";
		memset(dp,0,sizeof(dp));
		cout <<findMax(1,n) << endl;
	}
}

주: 사고방식은 합숙팀 콜드백 선배에서 유래한 것이다. 감사합니다.

3. 동그라미로 둘러싸다

합석자환형 이때 우리 dp수조의 의미는 dp[i][j]가 i번째 원소부터 뒤로 가는 j개 원소의 최소(최대)값을 나타냈다. 왜냐하면 다섯 개의 원소가 있으면 dp[1][5]dp[2][5]...dp[5][5]는 이 몇 개의 값이 대략적으로 다르기 때문이다.

어떻게 권의 문제를 해결합니까?

아이디어 1:

강제로 그를 동그라미로 둘러싸고 모형 연산 방법을 운용하다

for(int i = 2; i <= n; i++)//    
		{
			for(int j = 1; j <= n; j++)//     
			{
				dp_max[j][i] = -1;
				dp_min[j][i] = MAX;
				for(int k = 1; k < i; k++)
				{
					dp_max[j][i] = max(dp_max[j][i], dp_max[j][k] + dp_max[(j+k-1) % n + 1][i - k] + cost(j, i));
					dp_min[j][i] = min(dp_min[j][i], dp_min[j][k] + dp_min[(j+k-1) % n + 1][i - k] + cost(j, i));
				}
			}
		}

(j+k-1)%n+1 1부터 n까지 바로 1을 이어받아 완벽하게 0을 피했다

사고방식2:

두 배의 수조를 열고 원소를 원래의 순서대로 뒤에 복제한다. 예를 들어 예시: 3, 1, 2, 3. 우리는 이렇게 데이터를 저장한다. 1, 2, 3, 1, 2, 3. 이렇게 하면 동그라미가 된다. 좋지 않니?

for(int i = 1; i <= n; i++)
		{
			scanf("%d", &a[i]);
			a[i + n] = a[i];//     
			dp_min[i][i] = 0;
			dp_min[i + n][i + n] = 0; 
		}

그리고 어렵지 않을 거예요. 여기는 dp 부분이에요.

for(int len = 2; len <= n; len++)//    
		{
			for(int i = 1; len + i - 1 <= 2 * n; i++)//     
			{
				int j = len + i - 1;
				for(int k = i; k < j; k++)
				{
					dp_min[i][j] = min(dp_min[i][j], dp_min[i][k] + dp_min[k + 1][j] + cost[j] - cost[i - 1]);
					dp_max[i][j] = max(dp_max[i][j], dp_max[i][k] + dp_max[k + 1][j] + cost[j] - cost[i - 1]);
				}
			}
		}

그리고 AC라:

#include
#include
#include
using namespace std;
int n;
int dp_max[207][207];
int dp_min[207][207];
int cost[207];
int a[203];
const int MAX = 0x3f3f3f3f;

int main()
{
	while(scanf("%d", &n) != EOF)
	{
		memset(dp_min, MAX, sizeof(dp_min));
		memset(dp_max, 0, sizeof(dp_max));
		for(int i = 1; i <= n; i++)
		{
			scanf("%d", &a[i]);
			a[i + n] = a[i];
			dp_min[i][i] = 0;
			dp_min[i + n][i + n] = 0; 
		}
		cost[0] = 0;
		
		for(int i = 1; i <= 2 * n; i++)//          
		cost[i] = cost[i - 1] + a[i];
		
		for(int len = 2; len <= n; len++)//    
		{
			for(int i = 1; len + i - 1 <= 2 * n; i++)//     
			{
				int j = len + i - 1;
				for(int k = i; k < j; k++)
				{
					dp_min[i][j] = min(dp_min[i][j], dp_min[i][k] + dp_min[k + 1][j] + cost[j] - cost[i - 1]);
					dp_max[i][j] = max(dp_max[i][j], dp_max[i][k] + dp_max[k + 1][j] + cost[j] - cost[i - 1]);
				}
			}
		}
		int ans_min = MAX;
		int ans_max = -1;
		for(int i = 1; i <= n; i++)
		{
			ans_min = min(ans_min, dp_min[i][i+n-1]);
			ans_max = max(ans_max, dp_max[i][i+n-1]);
		}
		cout << ans_min << " " << ans_max << endl;
	}
	return 0;
}