Ban bong bay

Level 4
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.



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


Case #1
11348
Case #2
14700
Case #3
30759
Case #4
29289
Case #5
43110
Case #6
26688
Case #7
4642
Case #8
24722
Case #9
21370
Case #10
42823
Case #11
45302
Case #12
22323
Case #13
46499
Case #14
35378
Case #15
23460
Case #16
43860
Case #17
40820
Case #18
44986
Case #19
42591
Case #20
42858
Case #21
16636
Case #22
36599
Case #23
44268
Case #24
12363
Case #25
15762
Case #26
17937
Case #27
40936
Case #28
27488
Case #29
12726
Case #30
26798
Case #31
22200
Case #32
28107
Case #33
10575
Case #34
18005
Case #35
14232
Case #36
9401
Case #37
53312
Case #38
14114
Case #39
10899
Case #40
15355
Case #41
13219
Case #42
48610
Case #43
78606
Case #44
10
Case #45
62128
Case #46
30096
Case #47
16192
Case #48
26829
Case #49
21340
Case #50
21340
Time: 0.46400 s.

50
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
9
81 98 69 49 36 19 56 43 33
5
49 65 28 13 32
9
55 97 46 10 12 13 28 12 94
10
1 1 80 90 1 1 80 80 1 1
10
88 77 1 1 99 77 1 1 77 66
9
90 70 30 93 86 92 17 29 59
9
49 26 22 17 74 65 10 55 60
9
99 31 28 79 82 77 95 86 19
9
10 64 42 100 42 32 81 17 68
10
1 10 19 56 90 75 42 92 24 1
10
84 88 44 29 85 43 27 67 32 71
10
63 37 18 82 71 32 15 56 74 98
10
47 29 94 43 45 82 88 30 21 78
10
38 28 88 54 45 79 86 45 14 79
10
62 46 30 93 27 46 69 59 16 77
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
6
33 46 31 87 70 45
5
29 88 94 44 74
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
8
85 29 45 73 39 76 43 11
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
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
9
85 95 83 95 100 93 72 65 18
10
99 99 99 99 99 99 99 99 99 99
10
1 1 1 1 1 1 1 1 1 1
10
88 88 88 88 88 88 88 88 88 88
10
99 99 99 99 99 1 1 1 1 1 
10
1 1 1 88 88 88 88 1 1 1
10
88 88 1 1 1 1 1 1 99 99
10
1 55 1 55 1 55 1 55 1 55
10
55 1 55 1 55 1 55 1 55 1
 #include <iostream>
#include <time.h>

using namespace std;

int oo = 2000000000;

int T, n;
int vs[11], arr[11];
long long result;

int Max(int a, int b) {return (a > b ? a : b);}

void countLR(int index, int &l, int &r){
	int ans = 0;
	l = index - 1;
	r = index + 1;
	while(l >= 0 && vs[l] != 0) l--;
	while(r < n && vs[r] != 0) r++;
}

void backtrack(int index, long long total){
	if(index == n){
		if(result < total) result = total;
		return;
	}

	for(int i = 0; i < n; i++){
		if(vs[i] == 0){
			vs[i]++;

			int l, r;
			countLR(i, l, r);
			if(l >= 0 && r < n && index == n - 3){
				int m1 = arr[l] * arr[r] + 2 * Max(arr[l], arr[r]);
				int m2 = 3 * Max( Max(arr[i], arr[l]), Max(arr[i], arr[r]) );
				backtrack(index + 3, total + Max(m1, m2));
			}else if(l >= 0 && r < n){
				backtrack(index + 1, total + arr[l] * arr[r]);
			}

			vs[i]--;
		}
	}

}

int main(){
	// read input
	freopen("input.txt", "r", stdin);

	//calc time
	clock_t tStart, tStop;
	tStart = clock();

	cin >> T;
	
	for(int tc = 1; tc <= T; tc++){
		// input and initial
		cin >> n;
		for(int i = 0; i < n; i++){
			cin >> arr[i];
			vs[i] = 0;
		}
		result = 0;

		// solve problem
		backtrack(0, 0);

		// output
		cout << "Case #" << tc << "\n" <<  result << "\n";
	}


	//calc time
	tStop = clock();
	cout.setf(ios::fixed);
	cout.precision(5);
	cout << "Time: " << double(tStop - tStart) / CLOCKS_PER_SEC << " s." << endl;

	return 0;
}