API tools faq
paste
Advertisement
i_love_rao_khushboo

Burst Balloons

i_love_rao_khushboo
Sep 26th, 2022
883
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 9.06 KB | None | 0 0
raw download clone embed print report
  1. // RECURSIVE APPROACH
  2.  
  3. #include<bits/stdc++.h>
  4. using namespace std;
  5.  
  6. #define ll long long
  7. #define ld long double
  8. #define ull unsigned long long
  9. #define pb push_back
  10. #define ppb pop_back
  11. #define mp make_pair
  12. #define F first
  13. #define S second
  14. #define PI 3.1415926535897932384626
  15. #define sz(x) ((int)(x).size())
  16.  
  17. typedef pair<int, int> pii;
  18. typedef pair<ll, ll> pll;
  19. typedef vector<int> vi;
  20. typedef vector<ll> vll;
  21. typedef vector<ull> vull;
  22. typedef vector<bool> vb;
  23. typedef vector<char> vc;
  24. typedef vector<pii> vpii;
  25. typedef vector<pll> vpll;
  26. typedef vector<vi> vvi;
  27. typedef vector<vll> vvll;
  28. typedef vector<vull> vvull;
  29. typedef vector<vb> vvb;
  30. typedef vector<vc> vvc;
  31.  
  32. /************************************************** DEBUGGER *******************************************************************************************************/
  33.  
  34. #ifndef ONLINE_JUDGE
  35. #define debug(x) cerr << #x <<" "; _print(x); cerr << endl;
  36. #else
  37. #define debug(x)
  38. #endif
  39.  
  40. void _print(ll t) { cerr << t; }
  41. void _print(int t) { cerr << t; }
  42. void _print(string t) { cerr << t; }
  43. void _print(char t) { cerr << t; }
  44. void _print(ld t) { cerr << t; }
  45. void _print(double t) { cerr << t; }
  46. void _print(ull t) { cerr << t; }
  47.  
  48. template <class T, class V> void _print(pair <T, V> p);
  49. template <class T> void _print(vector <T> v);
  50. template <class T> void _print(vector <vector<T>> v);
  51. template <class T> void _print(set <T> v);
  52. template <class T, class V> void _print(map <T, V> v);
  53. template <class T> void _print(multiset <T> v);
  54. template <class T, class V> void _print(pair <T, V> p) { cerr << "{"; _print(p.F); cerr << ","; _print(p.S); cerr << "}"; }
  55. template <class T> void _print(vector <T> v) { cerr << "[ "; for (T i : v) {_print(i); cerr << " "; } cerr << "]"; }
  56. template <class T> void _print(vector <vector<T>> v) { cerr << "==>" << endl; for (vector<T> vec : v) { for(T i : vec) {_print(i); cerr << " "; } cerr << endl; } }
  57. template <class T> void _print(set <T> v) { cerr << "[ "; for (T i : v) {_print(i); cerr << " "; } cerr << "]"; }
  58. template <class T> void _print(multiset <T> v) { cerr << "[ "; for (T i : v) {_print(i); cerr << " "; } cerr << "]"; }
  59. template <class T, class V> void _print(map <T, V> v) { cerr << "[ "; for (auto i : v) {_print(i); cerr << " "; } cerr << "]"; }
  60.  
  61. /*******************************************************************************************************************************************************************/
  62.  
  63. mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
  64. int rng(int lim) {
  65.     uniform_int_distribution<int> uid(0,lim-1);
  66.     return uid(rang);
  67. }
  68.  
  69. const int INF = 0x3f3f3f3f;
  70. const int mod = 1e9+7;
  71.  
  72. ll mod_exp(ll a, ll b) { a %= mod; if(a == 0) return 0LL; ll res = 1LL;
  73.                          while(b > 0) { if(b & 1) res = (res * a) % mod; a = (a * a) % mod; b >>= 1; } return res; }
  74.                          
  75. ll mod_inv(ll a) { return mod_exp(a, mod - 2); } // works only for prime value of "mod"
  76. ll GCD(ll a, ll b) { return (b == 0) ? a : GCD(b, a % b); }
  77.  
  78. /******************************************************************************************************************************/
  79.  
  80. int burst_balloon(vi &v, int i, int j) {
  81.     // base condition
  82.     if(i > j) return 0;
  83.    
  84.     // to store the final result
  85.     int res = INT_MIN;
  86.    
  87.     // "k loop scheme"
  88.     // this scheme tells that if in the subarray v[i....j] if v[k] is the
  89.     // last balloon to be bursted then what maximum profit we can obtain from v[i....j]
  90.     for(int k = i; k <= j; k++) {
  91.         int left = (k == i) ? 0 : burst_balloon(v, i, k - 1);
  92.         int right = (k == j) ? 0 : burst_balloon(v, k + 1, j);
  93.         int val = ((i == 0) ? 1 : v[i-1]) * v[k] * ((j == sz(v) - 1) ? 1 : v[j+1]);
  94.        
  95.         int tmp = val + left + right;
  96.         res = max(res, tmp);
  97.     }
  98.    
  99.     return res;
  100. }
  101.  
  102. void solve()
  103. {
  104.     int n; cin >> n;
  105.     vi v(n);
  106.     for(int i = 0; i < n; i++) cin >> v[i];
  107.    
  108.     cout << burst_balloon(v, 0, sz(v) - 1) << "\n";
  109. }
  110.  
  111. int main()
  112. {
  113.     ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  114.     srand(chrono::high_resolution_clock::now().time_since_epoch().count());
  115.  
  116.     // #ifndef ONLINE_JUDGE
  117.     //     freopen("input.txt", "r", stdin);
  118.     //     freopen("output.txt", "w", stdout);
  119.     // #endif
  120.    
  121.     // #ifndef ONLINE_JUDGE
  122.     //      freopen("error.txt", "w", stderr);
  123.     // #endif
  124.    
  125.     int t = 1;
  126.     // int test = 1;
  127.     // cin >> t;
  128.     while(t--) {
  129.         // cout << "Case #" << test++ << ": ";
  130.         solve();
  131.     }
  132.  
  133.     return 0;
  134. }
  135.  
  136. // Time complexity: Exponential
  137.  
  138. /*****************************************************************************************************/
  139.  
  140. // TABULATION IMPLEMENTATION
  141. // Using Gap Method
  142.  
  143. #include<bits/stdc++.h>
  144. using namespace std;
  145.  
  146. #define ll long long
  147. #define ld long double
  148. #define ull unsigned long long
  149. #define pb push_back
  150. #define ppb pop_back
  151. #define mp make_pair
  152. #define F first
  153. #define S second
  154. #define PI 3.1415926535897932384626
  155. #define sz(x) ((int)(x).size())
  156.  
  157. typedef pair<int, int> pii;
  158. typedef pair<ll, ll> pll;
  159. typedef vector<int> vi;
  160. typedef vector<ll> vll;
  161. typedef vector<ull> vull;
  162. typedef vector<bool> vb;
  163. typedef vector<char> vc;
  164. typedef vector<pii> vpii;
  165. typedef vector<pll> vpll;
  166. typedef vector<vi> vvi;
  167. typedef vector<vll> vvll;
  168. typedef vector<vull> vvull;
  169. typedef vector<vb> vvb;
  170. typedef vector<vc> vvc;
  171.  
  172. /************************************************** DEBUGGER *******************************************************************************************************/
  173.  
  174. #ifndef ONLINE_JUDGE
  175. #define debug(x) cerr << #x <<" "; _print(x); cerr << endl;
  176. #else
  177. #define debug(x)
  178. #endif
  179.  
  180. void _print(ll t) { cerr << t; }
  181. void _print(int t) { cerr << t; }
  182. void _print(string t) { cerr << t; }
  183. void _print(char t) { cerr << t; }
  184. void _print(ld t) { cerr << t; }
  185. void _print(double t) { cerr << t; }
  186. void _print(ull t) { cerr << t; }
  187.  
  188. template <class T, class V> void _print(pair <T, V> p);
  189. template <class T> void _print(vector <T> v);
  190. template <class T> void _print(vector <vector<T>> v);
  191. template <class T> void _print(set <T> v);
  192. template <class T, class V> void _print(map <T, V> v);
  193. template <class T> void _print(multiset <T> v);
  194. template <class T, class V> void _print(pair <T, V> p) { cerr << "{"; _print(p.F); cerr << ","; _print(p.S); cerr << "}"; }
  195. template <class T> void _print(vector <T> v) { cerr << "[ "; for (T i : v) {_print(i); cerr << " "; } cerr << "]"; }
  196. template <class T> void _print(vector <vector<T>> v) { cerr << "==>" << endl; for (vector<T> vec : v) { for(T i : vec) {_print(i); cerr << " "; } cerr << endl; } }
  197. template <class T> void _print(set <T> v) { cerr << "[ "; for (T i : v) {_print(i); cerr << " "; } cerr << "]"; }
  198. template <class T> void _print(multiset <T> v) { cerr << "[ "; for (T i : v) {_print(i); cerr << " "; } cerr << "]"; }
  199. template <class T, class V> void _print(map <T, V> v) { cerr << "[ "; for (auto i : v) {_print(i); cerr << " "; } cerr << "]"; }
  200.  
  201. /*******************************************************************************************************************************************************************/
  202.  
  203. mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
  204. int rng(int lim) {
  205.     uniform_int_distribution<int> uid(0,lim-1);
  206.     return uid(rang);
  207. }
  208.  
  209. const int INF = 0x3f3f3f3f;
  210. const int mod = 1e9+7;
  211.  
  212. ll mod_exp(ll a, ll b) { a %= mod; if(a == 0) return 0LL; ll res = 1LL;
  213.                          while(b > 0) { if(b & 1) res = (res * a) % mod; a = (a * a) % mod; b >>= 1; } return res; }
  214.                          
  215. ll mod_inv(ll a) { return mod_exp(a, mod - 2); } // works only for prime value of "mod"
  216. ll GCD(ll a, ll b) { return (b == 0) ? a : GCD(b, a % b); }
  217.  
  218. /******************************************************************************************************************************/
  219.  
  220. int burst_balloon(vi &v) {
  221.     int n = sz(v);
  222.     vvi dp(n, vi(n));
  223.    
  224.     for(int g = 0; g < n; g++) {
  225.         for(int i = 0, j = g; j < n; i++, j++) {
  226.             int res = INT_MIN;
  227.            
  228.             for(int k = i; k <= j; k++) {
  229.                 int left = (k == i) ? 0 : dp[i][k-1];
  230.                 int right = (k == j) ? 0 : dp[k+1][j];
  231.                 int val = ((i == 0) ? 1 : v[i-1]) * v[k] * ((j == n - 1) ? 1 : v[j+1]);
  232.                
  233.                 int tmp = val + left + right;
  234.                 res = max(res, tmp);
  235.             }
  236.            
  237.             dp[i][j] = res;
  238.         }
  239.     }
  240.    
  241.     return dp[0][n-1];
  242. }
  243.  
  244. void solve()
  245. {
  246.     int n; cin >> n;
  247.     vi v(n);
  248.     for(int i = 0; i < n; i++) cin >> v[i];
  249.    
  250.     cout << burst_balloon(v) << "\n";
  251. }
  252.  
  253. int main()
  254. {
  255.     ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  256.     srand(chrono::high_resolution_clock::now().time_since_epoch().count());
  257.  
  258.     // #ifndef ONLINE_JUDGE
  259.     //     freopen("input.txt", "r", stdin);
  260.     //     freopen("output.txt", "w", stdout);
  261.     // #endif
  262.    
  263.     // #ifndef ONLINE_JUDGE
  264.     //      freopen("error.txt", "w", stderr);
  265.     // #endif
  266.    
  267.     int t = 1;
  268.     // int test = 1;
  269.     // cin >> t;
  270.     while(t--) {
  271.         // cout << "Case #" << test++ << ": ";
  272.         solve();
  273.     }
  274.  
  275.     return 0;
  276. }
  277.  
  278. // Time complexity: O(n^3)
  279. // Space complexity: O(n^2)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!