这题给个思路

chinalixs

题目：给定一个非负整数数组，假定你的初始位置为数组第一个下标。

数组中的每个元素代表你在那个位置能够跳跃的最大长度。

请确认你是否能够跳跃到数组的最后一个下标。

例如：

A = [2,3,1,1,4],

return true.

A = [3,2,1,0,4],

return false.

格式：

第一行输入一个正整数n，接下来的一行，输入数组A[n]。如果能跳到最后一个下标，输出“true”，否则输出“false”

样例输入

52 0 2 0 1

样例输出

true

[C] 纯文本查看 复制代码

#include <stdio.h>[/size][/backcolor][/color]
int main()
{
        int i,n;
        scanf("%d",&n);
        int a[n];
        for(i=0;i<n;i++)
        {
                scanf("%d",&a[i]);
        }
        if(n==1)
        {
                if(a[0]==0)
                printf("true");
                else
                printf("false");
                
        }
        else
        {
                for(i=0;i<n-1;)
                {
                        i+=a[i];
                        if(i==n-1)
                        printf("true");
                        if(i>n-1)
                        printf("false");
                        if(a[i]==0)
                        {
                                if(i<n-1)
                                        printf("false");break;
                        }
                }
        }        
        return 0;
} 

lyogoo

明显错了， 人家是最大跳那么多步， 不是就跳那么多步， 所有每一次都是有多重跳法，不断下去而形成一颗数，你可以用深搜，找到一种结果就行了。。。

yes2

我也贴个代码，计蒜客过不去，不知道错在哪

[C] 纯文本查看 复制代码

#include <stdio.h>
#include <string.h>
#include <malloc.h>


int main()
{
        int n1;
        scanf("%d", &n1);
        int *psz = (int *)malloc(n1*sizeof(int));
        for (int n=0 ; n<n1 ; n++)
        {
                scanf("%d" , &psz[n]);
        }
        int nIndex = n1 - 2;
        int nEnd = n1 - 1;
        int nSuc = 0;
        while (nIndex >= 0)
        {
                if (nIndex + psz[nIndex] >= nEnd)
                {
                        nEnd = nIndex;
                        nSuc = 1;
                }
                else
                {
                        nSuc = 0;
                }
                nIndex--;
        }

        if (nSuc)
        {
                printf("true");
        }
        else
        {
                printf("false");
        }


        free(psz);

        return 0;
}

醉空流澈

⊙﹏⊙说实在的，我不喜欢算法也不擅长算法，也比较菜。
根据8楼 随意之水的一滴 大神的说法，将他的伪代码里的max和i的值改为0，得到以下代码，测试就能通过了，orz。
另外a[n]在OJ可以编译，但在正常编译器里是通不过的，测试环境，VC6，VS2013。

[C] 纯文本查看 复制代码

#include<stdio.h>
int main()
{
	int n,max=0;
	scanf("%d",&n);
	int a[n];
	for(int i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
	}
	for(int j=0;j<n;j++)
	{
		if(j>max)
		{
			printf("false");
			return 0;
		}
		if(j+a[j]>max)
			max=j+a[j];
	}
	printf("true");
	return 0;
}

Anonymouss

可以往回跳。。。。。
应该用bfs

fc111

帮你顶哈  等待大牛

lyogoo

lyogoo 发表于 2015-2-19 22:47
明显错了， 人家是最大跳那么多步， 不是就跳那么多步， 所有每一次都是有多重跳法，不断下去而形成一颗数 ...

当然，时间，时间复杂度很大，可以为了练代码去实现以下，应该有专门的算法，只是我不知道，我很水

chinalixs

lyogoo 发表于 2015-2-19 22:47
明显错了， 人家是最大跳那么多步， 不是就跳那么多步， 所有每一次都是有多重跳法，不断下去而形成一颗数 ...

我擦~搜噶死乃。。。我题都读错了。。。。

chinalixs

Anonymouss 发表于 2015-2-19 22:30
可以往回跳。。。。。
应该用bfs

看来要重新补数据结构啊。多谢了！

随意之水的一滴

这个只需要是不是能够走到就行，也就是一遍顺序遍历就行了。。。。。从1个开始，对这一个判断能到的最远距离，如果大于旧的最远距离，然后更新最远距离，如果下一个在最远距离内，那么久继续判断下一个点，如果下一个点不在，则程序结束false，下个是末尾则true
int max=1
for int i=1;i<n;i++
      if i>max then return false
      if i+go[i]>max then max=i+go[i]
return true

Anonymouss

chinalixs 发表于 2015-2-20 10:38
看来要重新补数据结构啊。多谢了！

不客气~