Advertisement
Guest User

Untitled

a guest
Feb 11th, 2012
381
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.48 KB | None | 0 0
  1. #include <iostream>
  2. #include <iomanip>
  3. #include <vector>
  4. #include <map>
  5. #include <string>
  6. #include <cstring>
  7. #include <set>
  8. #include <queue>
  9. #include <stack>
  10. #include <bitset>
  11. #include <algorithm>
  12. #include <cstdio>
  13. #include <cstdlib>
  14. #include <cmath>
  15.  
  16. using namespace std;
  17.  
  18. struct line
  19. {
  20.     int x, y, num;
  21. };
  22.  
  23. bool comp (line a, line b)
  24. {
  25.     if (a.x == b.x)
  26.         return a.y < b.y;
  27.  
  28.     return a.x < b.x;
  29. }
  30.  
  31. vector <line> lines;
  32. int d[500], c[500];
  33.  
  34. int f (int v)
  35. {
  36.     if (d[v])
  37.         return d[v];
  38.  
  39.     int i = v + 1, t, mx = 0;
  40.  
  41.     while (i < lines.size() && lines[i].x == lines[v].x)
  42.         i++;
  43.  
  44.     if (i == lines.size())
  45.         return d[v] = 1;
  46.  
  47.     while (i < lines.size() && lines[i].y < lines[v].y)
  48.     {
  49.         t = f(i);
  50.  
  51.         if (t > mx)
  52.         {
  53.             mx = t;
  54.             c[v] = i;
  55.         }
  56.  
  57.         i++;
  58.     }
  59.  
  60.     return d[v] = mx + 1;
  61. }
  62.  
  63. int main()
  64. {
  65.     freopen("input.txt", "r", stdin);
  66.     freopen("output.txt", "w", stdout);
  67.  
  68.     int n, i, j, a, b, mx = 1, mi = 0;
  69.     vector <int> ans;
  70.     line tl;
  71.  
  72.     cin >> n;
  73.  
  74.     for (i = 0; i < n; i++)
  75.     {
  76.         cin >> a >> b;
  77.  
  78.         tl.num = i + 1;
  79.         tl.x = a;
  80.         tl.y = b;
  81.  
  82.         lines.push_back(tl);
  83.  
  84.         c[i] = -1;
  85.     }
  86.  
  87.     sort(lines.begin(), lines.end(), comp);
  88.  
  89.     for (i = 0; i < lines.size(); i++)
  90.         if (f(i) > mx)
  91.         {
  92.             mx = d[i];
  93.             mi = i;
  94.         }
  95.  
  96.     while (mi != -1)
  97.     {
  98.         ans.push_back(mi);
  99.         mi = c[mi];
  100.     }
  101.  
  102.     cout << ans.size() << endl;
  103.  
  104.     reverse(ans.begin(), ans.end());
  105.  
  106.     for (i = 0; i < ans.size(); i++)
  107.         cout << lines[ans[i]].num << ' ';
  108.  
  109.     return 0;
  110. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement