Ban bong bay
quoc14
c_cpp
19 days ago
4.8 kB
3
Indexable
Never
Backtrack
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; }
Leave a Comment