Advertisement
Guest User

Untitled

a guest
Jul 20th, 2011
600
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.16 KB | None | 0 0
  1. #pragma comment(linker, "/STACK:64000000")
  2. #include <iostream>
  3. #include <vector>
  4. #include <map>
  5. using namespace std;
  6. #define INF 1000*1000*1000
  7. vector<pair<int,int> > line;
  8. int m;
  9. int path[60002][4] = {0};
  10. int dp[60002];
  11. int dfs(int k)
  12. {
  13.     if(dp[k] != -1)
  14.         return dp[k];
  15.  
  16.     int a = line[k].first;
  17.     int b = line[k].second;
  18.    
  19.     if(a <= m && b >= m)
  20.         return 0;
  21.  
  22.     int mn = INF;
  23.     for (int i = 0; i < line.size(); i++)
  24.     {
  25.         int L = line[i].first;
  26.         int R = line[i].second;
  27.         if(L > a && R > b && L <= b)
  28.         {
  29.             int r = dfs(i) + 1;
  30.             if( r < mn)
  31.             {
  32.                 mn = r;
  33.                 path[k][0] = L;
  34.                 path[k][1] = R;
  35.                 path[k][2] = i;
  36.             }
  37.         }
  38.     }
  39.     return dp[k] = mn;
  40. }
  41. int main()
  42. {
  43.     memset(dp,255,sizeof dp);
  44.     //freopen ("input.txt","r",stdin);
  45.     scanf ("%d",&m);
  46.     line.push_back(make_pair(-666666,0));
  47.     while(1)
  48.     {
  49.         int a,b;
  50.         scanf ("%d%d",&a,&b);
  51.         if(a == 0 && b == 0)
  52.             break;
  53.         line.push_back(make_pair(a,b));
  54.     }
  55.     int ans = dfs(0);
  56.     if(ans == INF)
  57.         puts ("No solution");
  58.     else
  59.     {
  60.         printf ("%d\n",ans);
  61.         int j = 0;
  62.         for (int i = 0; i < ans; i++)
  63.         {
  64.             printf ("%d %d\n",path[j][0],path[j][1]);
  65.             j = path[j][2];
  66.         }
  67.     }
  68.     return 0;
  69. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement