FARIDA - Princess Farida - SOLUTION

This is an easy DP problem, which can be solved using bottom-up DP.

Let us take an array a[] which keeps the number of coins ith monster keeps.

Lets make a new array dp[]

dp[0]=0;

and further for every index i

dp[i] = max(a[i] + dp[i-2], dp[i-1])

I hope you can implement the code yourself or refer to the following code:

	#include "bits/stdc++.h"
	using namespace std;
	typedef unsigned long long ull;
	typedef long long int ll;
	typedef vector<long long int> vi;
	typedef pair<int, int> ii;
	typedef vector<ii> vii;
	int main()
	{
	ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
	ll t;
	cin>>t;
	ll k=1;
	while(t--)
	{
	ll dp[10000];
	dp[0]=0;
	ll n;
	cin>>n;
	if(n==0)
	{
	cout<<"Case "<<k++<<": "<<0<<endl;
	continue;
	}
	if(n==1)
	{
	ll x;
	cin>>x;
	cout<<"Case "<<k++<<": "<<x<<endl;
	continue;
	}
	cin>>dp[1]>>dp[2];
	dp[2]=max(dp[1],dp[2]);
	for(int i=3;i<=n;i++)
	{
	ll x;
	cin>>x;
	dp[i]=max(x+dp[i-2],dp[i-1]);
	}
	cout<<"Case "<<k++<<": "<<dp[n]<<endl;
	}
	return 0;
	}
	/* freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	*/

view raw FARIDA - Princess Farida.cpp hosted with ❤ by GitHub