YauhenMardan

Untitled

Mar 13th, 2019
120
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.99 KB | None | 0 0
  1. #include <fstream>
  2. #include<iomanip>
  3.  
  4. double* arr;
  5. double** dp;
  6. int n;
  7.  
  8. double min(double a,double b);
  9. double getMinLen();
  10.  
  11. int main(int argc, const char * argv[]) {
  12. std::ifstream fin("in.txt");
  13. std::ofstream fout("out.txt");
  14. double lenght;
  15. fin>>n;
  16. arr=new double[n];
  17. for(int i=0;i<n;i++){
  18. fin>>arr[i];
  19. }
  20. lenght=getMinLen();
  21. fout<<std::fixed;
  22. fout<<std::setprecision(2)<<lenght<<"\n";
  23. return 0;
  24. }
  25. double min(double a,double b){
  26. return a<b ? a : b;
  27. }
  28. double getMinLen(){
  29. dp=new double*[n];
  30. for(int i=0;i<n;i++){
  31. dp[i]=new double[2];
  32. }
  33.  
  34. for (int i = 0; i < n; i++) {
  35. dp[i][0] = INT_MAX;
  36. dp[i][1] = INT_MAX;
  37. }
  38. dp[1][0] = 0;
  39. dp[1][1] = arr[1]-arr[0];
  40.  
  41. for (int i = 1; i < n - 1; i++) {
  42. dp[i][0] = dp[i - 1][1];
  43. long double left = arr[i+1] - arr[i];
  44. dp[i + 1][1] = min(dp[i][0], dp[i][1]) + left;
  45. }
  46. return dp[n - 1][1];
  47. }
Advertisement
Add Comment
Please, Sign In to add comment