FARIDA - Princess Farida
The link to the problem FARIDA - Princess Farida :
http://www.spoj.com/problems/FARIDA/
This is a dynamic programming problem. To simply describe the problem you have to select the index elements of an array that are not adjacent to each other. So as to make the maximum sum of selected indexes values of the array.
The CPP solution for the problem ARIDA - Princess Farida is
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; long long int a[10005],dp[10005]; long long int n; long long int sol(long long int i) { if(i>=n) return 0; if(i==n-1) return a[n-1]; if(dp[i]!=-1) return dp[i]; dp[i]=max((a[i]+sol(i+2)),sol(i+1)); return dp[i]; } int main() { int i,j,k,t; scanf("%d",&t); for(i=1;i<=t;i++) { scanf("%lld",&n); for(j=0;j<n;j++) scanf("%lld",&a[j]); memset(dp,-1,sizeof dp); printf("Case %d: %lld\n",i,sol(0)); } return 0; }Happy Coding.............
No comments:
Post a comment