fork download
copy 
  1. #include <iostream>
  2. #include <cmath>
  3. #include <algorithm>
  4. #include <climits>
  5. using namespace std;
  6.  
  7. #define MAX_NUMBER  100
  8.  
  9. class Solution {
  10. public:
  11.     int getMinimumAdjust(int *arr, int n, int targetMaxDiff) {
  12.         static int result1[MAX_NUMBER + 1], result2[MAX_NUMBER + 1];
  13.         if (n < 2)
  14.             return 0;
  15.  
  16.         int *prevResult = &result1[0], *curResult = &result2[0];
  17.  
  18.         //Initialize with the last element of array
  19.         for (int i = 0; i <= MAX_NUMBER; ++i)
  20.             prevResult[i] = abs(arr[n - 1] - i);
  21.  
  22.         // Run DP
  23.         int minK = 0, maxK = 0, curDiff = INT_MAX;
  24.         for (int i = n - 2; i >= 0; --i) {
  25.             for (int j = 0; j <= MAX_NUMBER; ++j) {
  26.                 minK = max(0, j - targetMaxDiff);
  27.                 maxK = min(MAX_NUMBER, j + targetMaxDiff);
  28.                 curResult[j] = INT_MAX;
  29.  
  30.                 for (int k = minK; k <= maxK; ++k)
  31.                     curResult[j] = min(curResult[j], abs(j - arr[i]) + prevResult[k]);
  32.             }
  33.  
  34.             swap(prevResult, curResult);
  35.         }
  36.  
  37.         curDiff = INT_MAX;
  38.         for (int i = 0; i <= MAX_NUMBER; ++i)
  39.             curDiff = min(curDiff, prevResult[i]);
  40.         return curDiff;
  41.     }
  42. };
  43.  
  44. int main() {
  45.     Solution so;
  46.  
  47.     int arr1[] = {1, 4, 2, 3};
  48.     int n = sizeof(arr1) / sizeof(arr1[0]);
  49.     int target = 1;
  50.  
  51.     cout << "Min Cost of arr1 is " << so.getMinimumAdjust(arr1, n, target) << endl;
  52.  
  53.     return 0;
  54. }
Success #stdin #stdout 0s 3096KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Min Cost of arr1 is 2
https://ideone.com/btd3WU
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

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!