it can be done in greedy
#include<stdio.h>
#include<iostream>
#include<stack>
using namespace std;
int main()
{
int n,i,j,count=0;
scanf("%d",&n);
int a[n+1],set=0;
a[0]=-1;
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
stack<int> s;
i=1;
j=n;
while(j!=1)
{
set=0;
for(i=1;i<=n;i++)
{
if(j-i<=a[i])
{printf("%d",i);
j=i;
count++;
s.push(i);
set=1;
}
if(set==1)
break;
}
}
printf("%d\n",count);
while(!s.empty()){
printf("\n%d",a[s.top()]);
s.pop();}
}
On Jan 7, 12:19 pm, Decipher <[email protected]> wrote:
> Given an array of integers, each element represents the max number of
> jumps can make forward. What is the minimum number of element
> selections to reach the end of the array (starting from the first
> element).
> Example: arr = 1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9
> Here the min # of selections is : 3
> with the sequence : 1-> 3 -> 8 ->9
> First element is 1, so can only go to 3.
> Second element is 3, so can make at most 3 jumps: eg to 5 or 8 or 9.
> If an element is 0, then cannot make any jumps
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
