Ban bong bay

mail@pastecode.io avatar
unknown
plain_text
a year ago
5.3 kB
1
Indexable
Never
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

*** output ***
#1 22323
#2 46499
#3 11348
#4 2916
#5 14700
#6 4697
#7 45302
#8 6716
#9 30759
#10 29289
#11 43110
#12 2240
#13 26688
#14 4642
#15 42591
#16 42858
#17 24722
#18 16636
#19 36599
#20 44268
#21 13157
#22 12363
#23 15762
#24 6076
#25 17937
#26 40936
#27 27488
#28 12726
#29 3854
#30 26798
#31 44986
#32 22200
#33 28107
#34 10575
#35 18005
#36 35378
#37 2852
#38 14232
#39 9401
#40 53312
#41 14114
#42 10899
#43 15355
#44 13219
#45 48227
#46 43860
#47 40820
#48 48610
#49 23851
#50 18419


*** code hien ***

#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;
}

*** my code ***
#include<iostream>
using namespace std;
#define MaxN 11

int N;
int map[MaxN];
int ans;
int visit[MaxN];
int remainI;

int getLeft(int k){
	for (int i = k-1; i >= 1; i--){
		if (visit[i] == 0) {
			return map[i];
		}
	}
	return -1;
}

int getRight(int k){
	for (int i = k+1; i <= N; i++){
		if (visit[i] == 0){
			return map[i];
		} 
	}
	return -1;
}

int shoot(int ballI){
	int valLeft = getLeft(ballI);
	int valRight = getRight(ballI);
	// co 2 bong ben canh
	if (valLeft != -1 && valRight != -1) {
		return valLeft*valRight;
	}
	// chi co bong ben trai
	else if (valLeft != -1 && valRight == -1) {
		remainI = valLeft;
		return valLeft;
	}
	// chi co bong ben phai
	else if (valLeft == -1 && valRight != -1) {
		remainI = valRight;
		return valRight;
	}
	// khong co bong ben canh
	else if (valLeft == -1 && valRight == -1) {
		return remainI;
	}
}

void Try(int point, int remain){
	if (remain == 0){
		if (point > ans) ans = point;
		return;
	}
	for (int i = 1; i <= N; i++){
		if (visit[i] == 0){
			visit[i] = 1;
			int p = shoot(i);
			Try(point+p, remain-1);
			visit[i] = 0;
		}
	}
}

int main(){
	freopen("input.txt", "r", stdin);
	int TC; cin >> TC;
	for (int tc = 1; tc <= TC; tc++){
		cin >> N;
		ans = 0;
		for (int i = 1; i <= N; i++) {
			cin >> map[i];
			visit[i] = 0;
		}

		Try(0,N);
		
		cout << "#" << tc << " " << ans << endl;
	}
}