##
__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 .

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;
}
```

This comment has been removed by the author.

ReplyDeleteThis comment has been removed by the author.

ReplyDeleteHi 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 :)

ReplyDeletehttp://www.spojsolutions.tk/

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.

ReplyDeleteHello 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 ??

ReplyDeleteThis 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