# Platforms

a guest
Jan 1st, 2012
125
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