过河问题,需要dp吗?每次能跳到的最远的地方,这样就能保证,跳跃次数最少了。感觉可以,但只过60%.
import java.io.*;
import java.util.*;
public class Main
{
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
int n = Integer.valueOf(in.nextLine());
String s = in.nextLine();
if (n == 0) {
System.out.println(-1);
continue;
}
String[] ss = s.split("\\s");
int[] a = new int[ss.length];
for (int i = 0; i < a.length; i++) {
a[i] = Integer.valueOf(ss[i]);
}
int count = 1;
int i = 0;
for (; i < a.length;) {
int step = a[i];
if (a[i] == 0) {
System.out.println(-1);
break;
}
if (i + a[i] >= a.length) {
System.out.println(count);
break;
}
int j = i + a[i];
for (; j > i && a[j] == 0; j--) {
}
if (j == i) {
System.out.println(-1);
break;
} else {
i = j;
count++;
}
}
}
}
}