FARIDA

Princess Farida

Link to the question : FARIDA 

HINT :

The question asks us to take the maximum number of gold coins from the monsters such that if m_1, m_2, m_3......m_n are the monsters then  you can take gold coin from monster m_i only if you had not taken from m_(i-1).
This can be solved very easily by dp. Let us take an array b[] such that b[i] stores the maximum number of gold coins you can get from m_1 to m_i monsters. So,
b[i] = max( gold coins taken from ith monster + b[j]) where 0<j<i-1 .

RECOMMENDED QUESTION :

After solving this dp question, you would love solving this question as well.

SOURCE CODE :

/* Princess Farida */

/* Sushant Gupta */



#include<iostream>

using namespace std;

int main()

{

    int t,k=1;

    cin>>t;

    while(t--)

    {

        int n,i,j;

        cin>>n;

        long long int a[n],b[n],max=0;



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

        {

            cin>>a[i];

            b[i]= 0;

        }

        b[0]= a[0];

        b[1]= a[1];

        for(i=2;i<n;i++)

        {

            for(j=0;j<i-1;j++)

            {

                if(b[i]< b[j] + a[i])

                    b[i]= b[j] + a[i];

            }

        }

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

        {

            if(max< b[i])

                max = b[i];

        }

        cout<<"Case "<<k++<<": "<<max<<endl;

    }



    return 0;

}