fork download
copy 
  1. import java.util.Scanner;
  2.  
  3. class Main{
  4. 	public static void main (String[] args) {
  5. 		final int MAX = 100001;
  6. 		Scanner sc = new Scanner(System.in);
  7.         int amount_of_pltf = sc.nextInt();
  8.         int[] energy, platforms,  list_of_pltf;
  9.         int[] heights = new int[MAX];
  10.         for (int i = 1; i <= amount_of_pltf; i++) heights[i] = sc.nextInt();
  11.  
  12.         energy = new int[MAX];
  13.         platforms = new int[MAX];
  14.         energy[1] = 0;
  15.     	energy[2] = Math.abs(heights[2] - heights[1]);
  16.     	platforms[1] = -1;
  17.     	platforms[2] = 1;
  18.  
  19.     	//В цикле вычисляем значения ячеек energy[j] и platforms[j](3 ≤ j ≤ amount_of_pltf)
  20. 	    for (int j = 3; j <= amount_of_pltf; j++){
  21. 	        if((energy[j-1] + Math.abs(heights[j] - heights[j-1])) < (energy[j-2] + 3 * Math.abs(heights[j] - heights[j-2]))){
  22. 	            energy[j] = energy[j-1] + Math.abs(heights[j] - heights[j-1]);
  23. 	            platforms[j] = j - 1;
  24. 	        } else {
  25. 	            energy[j] = energy[j-2] + 3 * Math.abs(heights[j] - heights[j-2]);
  26. 	            platforms[j] = j - 2;
  27. 	        }
  28. 	    }
  29.  
  30. 	    //В переменной final_amount вычисляем конечное количество платформ, по которым нужно пройти.
  31. 	    int final_amount = 0;
  32. 	    list_of_pltf = new int[MAX];
  33. 	    for (int l = amount_of_pltf; l > 0; l = platforms[l]) list_of_pltf[final_amount++] = l;
  34.  
  35.     	System.out.println(energy[amount_of_pltf] + "\n" + final_amount);
  36. 	    for(int k = final_amount - 1; k >= 0; k--) System.out.print(list_of_pltf[k] + " ");
  37. 	}
  38. }
Success #stdin #stdout 0.13s 39612KB
comments (?)
stdin
copy 
5
0 1 0 1 0
stdout
copy 
0
3
1 3 5
https://ideone.com/BCPH6I
798
language:
Java (HotSpot 12)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!