fork(1) download
  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
stdin
5
0 1 0 1 0
stdout
0
3
1 3 5