CAPTTLE - EDITORIAL

editorial
, , ,
1

Problem

Problem CAPTTLE Problem - CodeChef

CODE RUSH 1.0 Contest Link:Contest Page | CodeChef

Author: Naman Gupta
Tester: Krish Murarka
Editorialist: Krish Murarka

DIFFICULTY:

EASY-Medium

PREREQUISITES:

Dynamic Programming

PROBLEM:

Assuming Keeper had “n” bottles in a row and also decided the price of bottles depending upon quantity and type of rum. Therefore; For each bottle in the row of “n” bottles, he decided the price Ai(where i=1,2,3……n and Ai is the number of gold coins he sells the "i"th bottle ) and also decides to sell one bottle every year.

Now he sells each bottle either from the start or the end of the row so as to maximize his profit from the gold coins which he gets after selling the rum bottles.

EXPLANATION:

This Question is based on the Inclusion/exclusion Principle of Dynamic Programming.
we have only two choices, either we can select the bottom from first or from the last and if we select a bottom from first we increment the front index and if we select the last bottle then we decrease the last index by one .so we just write these two recursive statements and the base case would reach when indexing of the last element < front index.

SOLUTION

Setters Solution

Solutions

#include <bits/stdc++.h>

#include

#include

#include

#include

#include

#include

#define endl “\n”

#define ll long long int

#define vi vector

#define vll vector

#define vvi vector

#define pii pair<int, int>

#define pll pair<long long, long long>

#define mod 1000000007

#define inf 1000000000000000001;

#define all(c) c.begin(), c.end()

#define mp(x, y) make_pair(x, y)

#define mem(a, val) memset(a, val, sizeof(a))

#define eb emplace_back

#define f first

#define s second

using namespace std;

int wineDP(int wines[], int i, int j, int y, int dp[][100])

{

//Base Case

if (i > j)

    return 0;

if (dp[i][j] != 0)

    return dp[i][j];

int op1 = wines[i] * y + wineDP(wines, i + 1, j, y + 1, dp);

int op2 = wines[j] * y + wineDP(wines, i, j - 1, y + 1, dp);

//cout << max(op1, op2) << endl;

return dp[i][j] = max(op1, op2);

}

int main()

{

std::ios::sync_with_stdio(false);

int n;

cin >> n;

int wines[n];

for(int i=0;i<n;i++)

{

    cin >> wines[i];

}

int dp[100][100] = {0};

cout << wineDP(wines, 0, n-1, 1, dp) << endl;

// Calculating total time taken by the program.

return 0;

}

1 Like