2>book shelf(given q explanation and soln in cpp)

#1

As exams are starting soon, you plan to buy books from the book store. There, you find out a particular shelf of books pretty interesting and therefore you plan to buy the whole shelf (row) for yourself. However this a special book store and there is a special rule for buying books.

You are given an array of integers representing the cost of the books. For buying a particular book you will need to pay an amount equal to the product of {cost of that book * cost of immediate left book * cost of immediate right book}. After this that book comes out of the shelf and now the immediate left and right books become adjacent.

However as you don’t have much time left for the exams you are going to pick books in any random order. To prepare for the worst outcomes calculate the maximum amount of money you will need if you take out books in a hurry and don’t really care for the cost.

Note: Here you may assume that the immediate left neighbour of the leftmost book has a cost value of 1 and the immediate right neighbour of the rightmost book has a cost value of 1.
Input Format

First line of input contains an integer N denoting the size of the book shelf. The second line contains N integers denoting the cost of the books.
Constraints

N<=500
0<=Cost of the books<=2000
Output Format

Print on a single line the maximum amount of money you will need to pay.
Sample Input

4
3 1 5 8

Sample Output

167

Explanation

The shelf looks like [3, 1, 5, 8]
We will buy book 2, hence the cost will be 3 * 1 * 5=15
The shelf looks like [3, 5, 8]
We will buy book 2, hence the cost will be 3 * 5 * 8=120
The shelf looks like [3, 8]
We will buy book 1, hence the cost will be 1 * 3 * 8=24
The shelf looks like [8]
We will buy book 1, hence the cost will be 1 * 8 * 1=8
The shelf looks like [ ]
Therefore our total cost is 15+120+24+8=167
Here if we pick out books in any other order, it is guaranteed that the answer will be <=167. Hence our final answer is 167.

#2

Send me the name of the problem if it’s in your course. Else if it’s not from your course then send me the link for this problem.

#3

it was asked in codcapsuel dec edition so i can provide u only info bro

#4

Have you tried solving this question on your own?

#5

yeah I tried on my own before posting doubts :slight_smile:

#6

Tell me the approach you are using to solve this question i will correct that.

#7

i tried running loop adding and removing the counted one but not clear approch

#8

This question will be solved by using this approach. In this it’s given for minimum. But you can calculate for maximum by just changing min to max condition. And also apply the conditions given in question. I won’t give you solution cause i can see that you don’t code. So i want you to try it on your own


Read this editorial and you will get the intuition.

#9

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

#10

@mr.encoder

#include<bits/stdc++.h>

using namespace std;
long long a[2005], dp[2005][2005]={0};

long long maxSum(int l, int r){
    if(r-l <= 1)    return dp[l][r] = 0;
    if(dp[l][r] != -1)    return dp[l][r];
    
    long long m = 0;
    for(int i=l+1;i<r;i++){
        int le = maxSum(l,i);
        int ri = maxSum(i,r);
        m = max(m, le + a[l]*a[i]*a[r] + ri);
    }
    return dp[l][r] = m;
}

int main(){
    int n;
    cin>>n;
    a[0]=1;
    memset(dp, -1, sizeof(dp));
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    a[n+1]=1;
    cout<<maxSum(0,n+1)<<endl;
    return 0;
}

This the code. I am getting WA for 2 test cases. Why? Pls Explain.