fork(1) download
copy 
  1. #include <iostream>
  2. #include <cmath>
  3. using namespace std;
  4.  
  5. #define MAX 100001
  6.  
  7. int main() {
  8. 	int amount_of_pltf;
  9. 	int heights[MAX], energy[MAX], platforms[MAX], list_of_pltf[MAX];
  10. 	cin >> amount_of_pltf;
  11. 	for (int i = 1; i <= amount_of_pltf; i++) cin >> heights[i];
  12.  
  13. 	energy[1] = 0;
  14. 	energy[2] = abs(heights[2] - heights[1]);
  15. 	platforms[1] = -1;
  16. 	platforms[2] = 1;
  17.  
  18. 	//В цикле вычисляем значения ячеек energy[j] и platforms[j](3 ≤ j ≤ amount_of_pltf)
  19. 	for (int j = 3; j <= amount_of_pltf; j++){
  20. 		if((energy[j-1] + abs(heights[j] - heights[j-1])) < (energy[j-2] + 3 * abs(heights[j] - heights[j-2]))){
  21. 			energy[j] = energy[j-1] + abs(heights[j] - heights[j-1]);
  22. 			platforms[j] = j - 1;
  23. 		} else {
  24. 			energy[j] = energy[j-2] + 3 * abs(heights[j] - heights[j-2]);
  25. 			platforms[j] = j - 2;
  26. 		}
  27. 	}
  28.  
  29. 	//В переменной final_amount вычисляем конечное количество платформ, по которым нужно пройти.
  30. 	int final_amount = 0;
  31. 	for (int l = amount_of_pltf; l > 0; l = platforms[l]) list_of_pltf[final_amount++] = l;
  32.  
  33. 	//Выводим результат. Минимальное количество энергии,
  34. 	//которое следует потратить для попадания с первой платформы на последнюю, равно energy[amount_of_pltf].
  35. 	cout << energy[amount_of_pltf] << "\n" << final_amount << "\n";
  36. 	for(int k = final_amount - 1; k >= 0; k--) cout << list_of_pltf[k] << " ";
  37. 	return 0;
  38. }
Success #stdin #stdout 0s 4392KB
comments (?)
stdin
copy 
5
0 1 0 1 0
stdout
copy 
0
3
1 3 5
https://ideone.com/zZtcO1
Платформы (на публикацию)
language:
C++ (gcc 8.3)
created:
5 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!