Advertisement
Guest User

Untitled

a guest
Nov 25th, 2014
141
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.55 KB | None | 0 0
  1. #include <cstdio>
  2. #include<conio.h>
  3. #include <algorithm>
  4. #include <stack>
  5. #include <stdio.h>
  6. #include <iostream>
  7. #include <fstream>
  8. using namespace std;
  9.  
  10. class WeightedInterval {
  11. public:
  12. int start, finish, weight;
  13.  
  14. bool operator < (const WeightedInterval& x) const {
  15. if (finish != x.finish)
  16. return finish < x.finish;
  17. }
  18. } *intervals;
  19.  
  20. int binary_search(int lo, int hi, int val) {
  21. int mid;
  22. while (lo < hi) {
  23. mid = lo + (hi - lo + 1) / 2;
  24. if (intervals[mid].finish <= val)
  25. lo = mid;
  26. else
  27. hi = mid - 1;
  28. }
  29. if (intervals[lo].finish > val)
  30. return 0;
  31. return lo;
  32. }
  33.  
  34. int greatestNonOverlappingInterval(int i) {
  35. return binary_search(0, i-1, intervals[i].start);
  36. }
  37.  
  38. int main() {
  39. int N, i = 1, *dp, *p;
  40. int start, fin, weight;
  41. fstream myfile("plik.txt", ios_base::in);
  42. myfile >> N;
  43. intervals = new WeightedInterval[N + 1];
  44. while(i <= N)
  45. {
  46. myfile >> start;
  47. myfile >> fin;
  48. weight = abs(start-fin);
  49. intervals[i].start = start;
  50. intervals[i].finish = fin;
  51. intervals[i].weight = weight;
  52. i++;
  53. }
  54.  
  55. sort(intervals + 1, intervals + N + 1);
  56.  
  57. dp = new int[N + 1];
  58. p = new int[N + 1];
  59. dp[0] = p[0] = 0;
  60.  
  61. for (i = 1; i <= N; i++)
  62. {
  63. p[i] = greatestNonOverlappingInterval(i);
  64. dp[i] = max(intervals[i].weight + dp[p[i]], dp[i-1]);
  65.  
  66. }
  67. printf("%d\n", dp[N]);
  68. return 0;
  69. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement