fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. int n, a[10], score = 0;
  5.  
  6. int findLeftNeighbour(int pos) {
  7.     if (pos < 0) return -1;
  8.     for (int i = pos - 1; i >= 0; --i)
  9.         if (a[i] != 0) return i;
  10.     return -1;
  11. }
  12.  
  13. int findRightNeighbour(int pos) {
  14.     if (pos >= n) return -1;
  15.     for (int i = pos + 1; i < n; ++i)
  16.         if (a[i] != 0) return i;
  17.     return -1;
  18. }
  19.  
  20. void solve(int nBurst, int curScore) {
  21.     if (nBurst == n) {
  22.         if (score < curScore) score = curScore;
  23.         return;
  24.     }
  25.  
  26.     for (int i = 0; i < n; ++i) {
  27.         if (a[i] != 0) {  // if not already burst (a[i] == 0 => balloon burst at a[i])
  28.             // burst current balloon and calc score
  29.             int left = findLeftNeighbour(i);
  30.             int right = findRightNeighbour(i);
  31.             int tempScore;
  32.             if (left != -1 && right != -1)  // left, right both are present
  33.                 tempScore = a[left] * a[right];
  34.             else if (left != -1 && right == -1)  // left is present
  35.                 tempScore = a[left];
  36.             else if (right != -1 && left == -1)  // right is present
  37.                 tempScore = a[right];
  38.             else if (left == -1 && right == -1)  // neither left nor right is present
  39.                 tempScore = a[i];
  40.  
  41.             int tempCurVal = a[i];
  42.             // mark as burst
  43.             a[i] = 0;  // (as a[i] > 0)
  44.             // solve further
  45.             solve(nBurst + 1, curScore + tempScore);
  46.             // backtrack
  47.             a[i] = tempCurVal;
  48.         }
  49.     }
  50. }
  51.  
  52. int main() {
  53.     int t;
  54.     cin >> t;
  55.     while (t--) {
  56.         cin >> n;
  57.         for (int i = 0; i < n; ++i) cin >> a[i];
  58.  
  59.         solve(0, 0);
  60.         cout << score << endl;
  61.     }
  62.  
  63.     return 0;
  64. }
  65.  
  66. /*
  67.  
  68. sample testcase:
  69. 5
  70. 4
  71. 1 2 3 4
  72. 5
  73. 3 10 1 2 5
  74. 7
  75. 12 48 28 21 67 75 85
  76. 8
  77. 245 108 162 400 274 358 366 166
  78. 10
  79. 866 919 840 944 761 895 701 912 848 799
  80.  
  81. output:
  82. 20
  83. 100
  84. 16057
  85. 561630
  86. 6455522
  87.  
  88. */
Success #stdin #stdout 0.17s 4260KB
comments (?)
stdin
copy 
5
4
1 2 3 4
5
3 10 1 2 5
7
12 48 28 21 67 75 85
8
245 108 162 400 274 358 366 166
10
866 919 840 944 761 895 701 912 848 799
stdout
copy 
20
100
16057
561630
6455522
https://ideone.com/DTzUEL
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!