Friday, 24 July 2015

FARIDA

Standard


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;

}



  

6 comments:

  1. This comment has been removed by the author.

    ReplyDelete
  2. This comment has been removed by the author.

    ReplyDelete
  3. Hi shushant! i am too writing a blog on spoj solutions, and i am trying to apply for adsense! well i am really encouraged and happy after seeing, you've got adsense approval on a similar blog. Well, my content is original, so can you please my blog and tell me what should i do to get adsense approval! Thanx in advance :)

    http://www.spojsolutions.tk/

    ReplyDelete
  4. I got an approval for adsense after 7-8 months of starting my blog. I did not to do anything special for that. Just used to post one or two post in a week and one fine day got a notification that it has been approved.

    ReplyDelete
  5. Hello Sushant Can you tell me what is meant by non -recursive Dp , what are you using recursive or non recursive, i am confused , i used recursive and I got 0.05 in spoj but many have 0.02 how ??

    ReplyDelete
    Replies
    1. This solution of mine uses non recursive, i.e iterative approach. By recursive dp I guess you mean memoization. And regarding time, others might have used fast I/O.

      Delete