当前位置：网站首页>[dynamic planning]dp27 jumping game (II) - medium

[dynamic planning]dp27 jumping game (II) - medium

2022-07-19 12:50:00 【51CTO】

describe

Given an array of nonnegative integers nums, Assume that the initial subscript is 0 The location of , Each element in the array represents the maximum length of the next hop , If you can skip to the last position of the array , Please find out the most integral you can get in the jumping path .

1. If you can jump to the last position of the array , To calculate the integral obtained , Otherwise, the integral value is -1

2. If you can't jump ( That is, the length of the array is 0), Please also return to -1

3. The data guarantees that the returned result will not exceed the shaping range , That is, it will not exceed

Data range :

Input description ：

Enter a positive integer in the first line n Represents an array nums The length of

Second line input n It's an integer , Represents an array nums The values of all elements of

Output description ：

Output the most points you can get

Example 1

Input ：

       
       6
       
4 2 1 0 100
      



Output ：

explain ：

       
        The first is in nums[0]=2, Then you can jump 1 Step , To nums[1]=4 The location of , integral =2+4=6, Jump to nums[5]=100 The location of , integral =6+100=106
       
 This ensures that you can jump to the last element of the array , And it can guarantee to get the most points 
      
1.
2.

Example 2

Input ：

       
       6
       
4 0 2 0 100
      



Output ：

explain ：

       
        The jumping path is ：2=>4=>2=>100, A total of 108
      
1.

Example 3

Input ：

       
       6
       
3 2 1 0 100
      



Output ：

explain ：

       
        Can't jump to the last position , return -1
      
1.

Answer key

Link to my Niuke website ~~

This question is a variant of jumping game one . Require maximum points , In fact, it is to find the maximum sum of all points on the path . Now we know the following conditions ( If there is any solution )：

Finally, it must stop at n-1 coordinate
If the coordinates of a node are i, The value of this coordinate is nums[i], For any greater than i The positive integer k, If you want to be able to jump to this position , There has to be i+nums[i]>=k

According to the above conditions, we can deduce in reverse , Use the greedy method to solve . Suppose we are in position k On , Then if you can from the position x < k Jump up to the position k On , We can nums[x] Add up to the total integral .

So how to determine whether it can be from x Jump up to k How about it ？ According to paragraph above 2 Point analysis , as long as x+nums[x] >= k that will do . That is to say nums[x] >= k - x, and k For the last stop ,x For the current coordinates we want to judge .k Starting at n-1,x Starting at n-2, As long as the above equation can be satisfied, it will x--, And then update k value . We don't use coordinates here , But use from k and x Between gap To solve it .gap Indicates the current coordinates i And the previous coordinate k Difference between .

The code is as follows ：

       
       #include <bits/stdc++.h>
       
       int 
       
       solve(
       
       const 
       
       std::vector
       
       <
       
       int
       
       > 
       
       &
       
       v)
       
{
       
       if (
       
       v.
       
       size() 
       
       <= 
       
       1)
       
  {
       
       return 
       
       std::accumulate(
       
       v.
       
       begin(), 
       
       v.
       
       end(), 
       
       0);
       
  }
       
       int 
       
       ans 
       
       = 
       
       v.
       
       back();
       
       //  Total points 
       
       int 
       
       gap 
       
       = 
       
       1;
       
       //  Between the previous step and the current step gap
       
       for (
       
       int 
       
       i 
       
       = 
       
       v.
       
       size() 
       
       - 
       
       2; 
       
       i 
       
       >= 
       
       0; 
       
       --
       
       i)
       
  {
       
       if (
       
       v[
       
       i] 
       
       >= 
       
       gap)
       
    {
       
       gap 
       
       = 
       
       1;
       
       ans 
       
       += 
       
       v[
       
       i];
       
       //  It can be downloaded from i Transfer to i+gap The location of , So accumulate v[i], And update gap by 1, Indicates whether it can be adjusted from the previous step to the current 
       
    }
       
       else 
       
       if (
       
       i 
       
       == 
       
       0)
       
    {
       
       return 
       
       -
       
       1;
       
       //  We have found the beginning , There is no solution 
       
    }
       
       else
       
    {
       
       gap
       
       ++;
       
       //  The current step cannot jump to gap+i On , Therefore, the next step needs to be gap Add one 
       
    }
       
  }
       
       return 
       
       ans;
       
}
       
       int 
       
       main()
       
{
       
       int 
       
       n;
       
       std::cin 
       
       >> 
       
       n;
       
       std::vector
       
       <
       
       int
       
       > 
       
       v(
       
       n);
       
       for (
       
       int 
       
       i 
       
       = 
       
       0; 
       
       i 
       
       < 
       
       n; 
       
       ++
       
       i)
       
  {
       
       std::cin 
       
       >> 
       
       v[
       
       i];
       
  }
       
       std::cout 
       
       << 
       
       solve(
       
       v) 
       
       << 
       
       std::endl;
       
       return 
       
       0;
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.