Advertisement
jeff69

Untitled

Sep 20th, 2016
84
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.25 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long LL;
  4. typedef long double ld;
  5. const int MX=1e5+9;
  6.  
  7. pair<LL,LL> dom[MX];
  8. int ar[MX],er[MX],n;
  9. map<pair<int,int>,int> dp;
  10. int solve(int st,int en)
  11. {
  12. if(st>en)return 0;
  13. if(dp[{st,en}]!=0)return dp[{st,en}]-1;
  14. int x=dom[st].first;
  15. int y=dom[st].second;
  16. int xx=dom[en].first;
  17. int yy=dom[en].second;
  18. int ans=0;
  19. // new st en or new en st
  20. int temp=x+y;
  21. int i;
  22. if(ar[st]!=-1)i=ar[st];
  23. else for( i=st;i<n;i++)
  24. {
  25. int ox,oy;
  26. ox=dom[i].first;
  27. oy=dom[i].second;
  28. if(temp>=ox)temp=max(temp,ox+oy);
  29. else break;
  30. }
  31. ar[st]=i;
  32. ans=1+solve(i,en);
  33. temp= xx-yy;
  34. if(er[en]!=-1)i=er[en];
  35. else for( i=en;i>=0;i--)
  36. {
  37. int ox,oy;
  38. ox=dom[i].first;
  39. oy=dom[i].second;
  40. if(temp<=ox)temp=min(temp,ox-oy);
  41. else break;
  42. }
  43. er[en]=i;
  44. ans=min(ans,1+solve(st,i));
  45. dp[{st,en}]=ans+1;
  46. return ans;
  47. }
  48. int main()
  49. {
  50. memset(er,-1,sizeof er);
  51. memset(ar,-1,sizeof ar);
  52. scanf("%d",&n);
  53. for(int i=0;i<n;i++)
  54. {
  55. scanf("%d%d",&dom[i].first,&dom[i].second);
  56. }
  57. sort(dom,dom+n);
  58. printf("%d",solve(0,n-1));
  59. return 0;
  60. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement