Untitled

Bắn Bóng Bay
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.

Khi 1 quả bóng bị vỡ, tất cả các quả bóng sẽ dồn lại gần nhau



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:

3

9

49 26 22 17 74 65 10 55 60

9

99 31 28 79 82 77 95 86 19

6

24 41 22 97 39 41

Ouput:

#1 22323

#2 46499

#3 11348







50
9
49 26 22 17 74 65 10 55 60
9
99 31 28 79 82 77 95 86 19
6
24 41 22 97 39 41
3
34 41 81
5
84 39 33 59 81
3
59 78 77
9
90 70 30 93 86 92 17 29 59
3
71 14 92
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
3
56 89 38
9
81 98 69 49 36 19 56 43 33
5
49 65 28 13 32
10
38 28 88 54 45 79 86 45 14 79
10
62 46 30 93 27 46 69 59 16 77
9
55 97 46 10 12 13 28 12 94
7
65 24 39 18 10 70 83
7
44 91 39 84 78 95 90
9
27 64 98 25 93 11 82 93 41
4
87 38 52 97
6
33 46 31 87 70 45
5
29 88 94 44 74
3
60 21 98
9
16 64 51 16 44 31 75 28 24
8
48 24 57 93 96 86 87 100
9
39 45 49 50 41 84 61 49 64
7
56 46 12 24 47 62 54
3
39 12 94
8
85 29 45 73 39 76 43 11
10
47 29 94 43 45 82 88 30 21 78
8
18 13 37 83 74 32 96 30
7
22 56 81 94 92 29 81
6
75 31 35 29 53 22
6
89 13 66 15 53 42
9
10 64 42 100 42 32 81 17 68
3
29 63 92
5
77 73 94 18 40
5
63 89 91 24 23
9
66 88 72 21 98 72 58 20 98
6
46 59 19 53 95 20
6
57 15 34 69 26 39
6
95 56 45 14 71 10
6
32 30 17 97 24 55
10
83 10 19 56 90 75 42 92 24 66
10
84 88 44 29 85 43 27 67 32 71
10
63 37 18 82 71 32 15 56 74 98
9
85 95 83 95 100 93 72 65 18
8
32 42 77 99 65 38 51 58
6
31 76 93 98 66 53



// CODE

#include <iostream>
using namespace std;

int N;
int a[10];
long long ans;

int move(int len, int k){
	int t = a[k];

	for(int i = k; i < len - 1; i++){
		a[i] = a[i+1];
	}
	a[len - 1] = 0;

	return t;
}

void unmove(int t, int k, int len){
	for(int i = len - 1; i > k; i--){
		a[i] = a[i - 1];
	}
	a[k] = t;
}

void Try(long long sum, int len){
	if(len == 2){
		int rs = a[0] >= a[1] ? a[0] : a[1];
		sum += rs*2;
		if(sum > ans) ans = sum;
		return;
	}

	for(int i = 1; i < len - 1; i++){
		int t = move(len, i);
		Try(sum + a[i-1] * a[i], len - 1);
		unmove(t, i, len);
	}
}

int main(){
	freopen("input.txt", "r", stdin);
	int T; cin >> T;

	for(int tc = 1; tc <= T; tc++){
		cin >> N;

		for(int i = 0; i < N; i++){
			a[i] = 0;
		}

		for(int i = 0; i < N; i++){
			cin >> a[i];
		}
		ans = -1;
		Try(0, N);

		cout << "#" << tc << " " << ans << endl;
	}
	 
	return 0;
}