Untitled

Cho N quả bóng bay với mỗi quả bóng bay có 1 giá trị số.
Người chơi được yêu cầu bắn vỡ các quả bóng bay để có được số điểm lớn nhất.

Điểm của người chơi sẽ được tính bằng tổng các lần bắn bóng bay.
Điểm của mỗi lần bắn bóng bay sẽ bằng tích của 2 quả bóng bay bên cạnh.

Nếu bên cạnh chỉ có 1 quả bóng bay thì điểm sẽ bằng điểm của quả bóng bay này.

Nếu không còn quả bóng bay nào bên cạnh thì điểm sẽ bằng điểm của quả bóng bay vừa bị bắn.



Hãy tìm điểm số lớn nhất và in ra.
N <=10

Điểm của các quả bóng <10000

Định dạng in ra như bên dưới.

input:

5
6
24 41 22 97 39 41
5
84 39 33 59 81
6
99 84 56 68 76 99
8
89 32 42 44 83 38 24 67
8
27 92 81 90 74 88 53 90

Ouput:
Case #1
11348
Case #2
14700
Case #3
30759
Case #4
29289
Case #5
43110


#define _CRT_SECURE_NO_WARNINGS
#include<iostream>

using namespace std;
#define Max_N 15

int T, N; 
long long ans;
int Map[Max_N];
int vis[Max_N];

int Sum_bong(int x)
{
	int l = x - 1, r = x + 1;
	while (l > 0 && vis[l])
	{
		l--;
	}
	while (r <= N && vis[r])
	{
		r++;
	}
	if(l > 0 || r <= N)
		return Map[l]*Map[r];
	return Map[x];
}

void backtrack(int index, long long sum)
{
	if(index == N + 1)
	{
		if(sum > ans)
			ans = sum;
		return;
	}

	if(N - index <= 3)
	{
		for (int i = 1; i <= N; i++)
		{
			if(!vis[i])
			{
				vis[i] = 1;
				backtrack(index + 1, sum + Sum_bong(i));
				vis[i] = 0;
			}
		}
	}
	else
	{
		for (int i = 2; i < N; i++)
		{
			if(!vis[i])
			{
				vis[i] = 1;
				backtrack(index + 1, sum + Sum_bong(i));
				vis[i] = 0;
			}
		}
	}
}

int main()
{
	freopen("input.txt","r",stdin);
	cin >> T;
	for (int tc = 0; tc < T; tc++)
	{
		cin >> N;
		Map[0] = Map[N+1] = 1;
		vis[0] = vis[N+1] = 1;

		for (int i = 1; i <= N; i++)
		{
			cin >> Map[i];
			vis[i] = 0;
		}
		ans = 0;
		backtrack(1,0);
		cout << "Case #" << tc + 1 << endl;
		cout << ans <<  endl;
	}
	return 0;
}