SHARE
TWEET

Platforms

a guest Jan 1st, 2012 71 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <string>
  4. #include <stack>
  5. #include <vector>
  6. #include <algorithm>
  7. #include <map>
  8. #include <set>
  9.  
  10. using namespace std;
  11.  
  12. long long dp1[1000000] , dp2[1000000] , a[1000000] , n;
  13.  
  14. inline long long sqr(long long a) { return a * a ; };
  15. inline long long absf(long long a) { return (a < 0) ? -a : a ; };
  16. int main()
  17. {
  18. //freopen("input.txt", "r", stdin);
  19. //freopen("output.txt", "w", stdout);
  20. scanf("%I64d",&n);
  21. for (int i = 1 ; i <= n ; i ++ )
  22.    scanf("%I64d",&a[i]);
  23. dp1[2] = absf(a[1] - a[2]);
  24. dp1[3] = min(dp1[2] + absf(a[2] - a[3]) , 3 * absf(a[1] - a[3]) );
  25. dp2[2] = sqr(a[1] - a[2]);
  26. dp2[3] = min(dp2[2] + sqr(a[2] - a[3]) , 3 * sqr(a[1] - a[3]) );
  27. for (int i = 4 ; i <= n ; i ++ )
  28. {
  29.    dp1[i] = min(dp1[i - 1] + absf(a[i - 1] - a[i]) , dp1[i - 2] + 3 * absf(a[i - 2] - a[i]) );
  30.    dp2[i] = min(dp2[i - 1] + sqr(a[i - 1] - a[i]) , min (
  31.                 dp2[i - 2] + 3 * sqr(a[i - 2] - a[i]) ,
  32.                 dp2[i - 3] + 3 * sqr(a[i - 1] - a[i - 3]) +
  33.                 sqr(a[i - 1] - a[i - 2]) + 3 * sqr(a[i] - a[i - 2])
  34.                 ) ) ;
  35. }
  36. cout << dp1[n] << " " << dp2[n] << endl;
  37. return 0;
  38. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top