ronith
10/29/2018 - 9:47 AM

Bursting Balloons

There are N Balloons marked with value Bi (where B(i…N)). User will be given Gun with N Bullets and user must shot N times. When any balloon explodes then its adjacent balloons becomes next to each other. User has to score highest points to get the prize and score starts at 0. Below is the condition to calculate the score. When Balloon Bi Explodes then score will be a product of Bi-1 & Bi+1 (score = Bi-1 * Bi+1). When Balloon Bi Explodes and there is only left Balloon present then score will be Bi-1. When Balloon Bi Explodes and there is only right Balloon present then score will be Bi+1. When Balloon Bi explodes and there is no left and right Balloon present then score will be Bi. Write a program to score maximum points.

//https://www.geeksforgeeks.org/samsung-semiconductor-institute-of-researchssir-software-intern-fte-set-2/
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin>>n;
    int arr[n];
    for (int i=0;i<n;i++)
        cin>> arr[i];

    int a[n+2];
    a[0]= 1;
    a[n+1]= 1;
    for (int i=1;i<=n;i++)
        a[i]= arr[i-1];

    int dp[n+2][n+2];
    memset (dp, 0, sizeof (dp));

    for (int len= 1;len<=n;len++) {
        for (int i=1;i<=n-len+1;i++) {
            int j= i+len-1;
            for (int k= i;k<=j; k++) {
                int c= dp[i][k-1]+dp[k+1][j];
                if (i== 1 && j== n)
                    c+= a[k];
                else
                    c+= a[i-1]*a[j+1];
                dp[i][j]= max(dp[i][j], c);

            }

        }
    }
    cout<< dp[1][n];
}