跳跃游戏(二)

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n = in.nextInt();
        int[] num = new int[n];
        int[] f = new int[n];
        int i;

        // 动态规划的过程，判断是否可达，将可达信息存储在f[i]中
        for(i = 0; i < n; i++){
            num[i] = in.nextInt();
        }
        f[0] = num[0];
        for(i = 1; i < n - 1 && i <= f[i-1]; i++){
            f[i] = Math.max(f[i-1], num[i] + i);
        }
        // 输出不可达信息
        if(f[i - 1] < n - 1){
            System.out.print(-1);
            return;
        }

        // 倒推，贪婪，从后往前只要可达的点都选择
        int sum = num[n - 1];
        int pos = n - 1;
        for(i = n - 2; i >= 0; i--){
            if(f[i] != 0 && num[i] + i >= pos){
                pos = i;
                sum += num[i];
            }
        }
        System.out.print(sum);
    }
}

#include <iostream>
#include <vector>
using namespace std;

int main() {

    int n;
    cin>>n;
    vector<int> arr(n);
    for(int i=0; i<n; i++){
        cin>>arr[i];
    }
    vector<int> dp(n,-1);
    dp[n-1] = arr[n-1];
    int pos = n-1, pre = pos;
    while(true){
        int j=pos-1;
        while(j>=0){
            if(arr[j]+j>=pos){ //说明从j位置可以一步跳到pos位置
                dp[j] = arr[j]+dp[pos];
                pos = j;
            }
            j--;
        }
        if(pre==pos||pos==0){ //pos没有向前推
            break;
        }
        pre = pos;
    }
    cout<<dp[0];

    return 0;
}

import sys

for line in sys.stdin:
    a = line.split()
nums = [int(t) for t in a]
pos = len(nums)-1
v = nums[-1]

for i in range(len(nums)-2, -1, -1):
    if nums[i] >= pos - i:
       pos = i 
       v += nums[i]

if pos != 0:
    print(-1)
else:
    print(v)

Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        if (n == 0) {
            System.out.println("-1");
            return;
        }
        int[] nums = new int[n];
        int[] dp = new int[n];  //保存 i 的位置是否可以到达的状态. 1可以到达, 0不可以到达
        for (int i = 0; i < n; i++) {
            nums[i] = in.nextInt();
        }

        //dp  动态规划 : 从数组最后往前遍历.. 能到达终点的终点的位置 标记 1.
        dp[n - 1] = 1; //终点位置标记1
        for (int i = n - 1; i >= 0; i--) {
            int num = nums[i];
            for (int j = i + num; j >= i; j--) { //遍历能到达的点.
                if (j >= n - 1 || dp[j] == 1) {//超过了终点 或者 到达的点 确定可以到达终点
                    dp[i] = 1;
                    break;
                } //否则 dp[i] 保持 0
            }
        }
        if (dp[0] == 0) { //开始的位置不能到达终点的话, 那么直接 返回-1
            System.out.println("-1");
            return;
        }
        int max = 0;
        for (int i = 0; i < n; i++) { //能到达的点都加上积分
            if (dp[i] == 1) max += nums[i];
        }

        System.out.println(max);

n = int(input())
nums = list(map(int,input().split(' ')))
idx = n-1
res = 0
while idx>0:
    res += nums[idx]
    j = idx-1
    while j>=0 and nums[j]+j<idx:
        j-=1
    if j<0:
        break
    idx = j
if idx>0:
    print(-1)
else:
    print(res+nums[0])

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        int[] a=new int[n];
        for(int i=0;i<n;i++){
            a[i]=in.nextInt();
        }
         int[] dp=new int[n];
        Arrays.fill(dp,-1);
        dp[0]=a[0];
        
        for(int i=0;i<n-1;i++){
            if(dp[i]<0||a[i]==0){
                
                continue;
            }
               int end=Math.max(n,i+a[i]+1);
                for(int s=i+1;s<end;s++){
                    dp[s]=Math.max(dp[s],dp[i]+a[s]);
                }  
            
           
        }
       
     
            System.out.println(dp[n-1]);
       
        
    }
}