设为首页 加入收藏

TOP

区间覆盖最小代价(二)
2013-02-08 14:29:57 来源: 作者: 【 】 浏览:460
Tags:区间 覆盖 最小 代价


  取最小的数可以用线段树做O(NlogN)。
  [cpp]
  #include<cstdio>
  #include<cstring>
  #include<cstdlib>
  #include<cmath>
  #include<cctype>
  #include<iostream>
  #include<functional>
  #include<algorithm>
  using namespace std;
  #define MAXN (10000+10)
  #define MAXE (86399)
  #define MAXS (500000+10)
  #define INF (9187201950435737471)
  int n,s,e;
  struct SegMent
  {
  int l,r;
  long long S;
  SegMent(){}
  SegMent(int _l,int _r,long long _S):l(_l),r(_r),S(_S){}
  friend bool operator<(const SegMent a,const SegMent b){return a.r<b.r;}
  }a[MAXN];
  struct SegMentTree //min()
  {
  int n,M;
  long long t[MAXE*10];
  void fillchar(int _n)
  {
  n=_n+2;
  M=1;while (M-2<n) M《=1;
  memset(t,127,sizeof(t));
  }
  void update(int x)
  {
  for (x>>=1;x;x>>=1) t[x]=min(t[x《1],t[(x《1)^1]);
  }
  void insert(int x,long long c)
  {
  x=x+2;
  x+=M;
  if (t[x]>c) {t[x]=c; update(x);  }
  }
  long long find(int l,int r)
  {
  l=l+2;r=r+2;
  l=l-1+M;r=r+1+M;
  long long ans=INF;
  while (l^r^1)
  {
  if (~l&1) ans=min(ans,t[l+1]);
  if (r&1) ans=min(ans,t[r-1]);
  l》=1;r》=1;
  }
  return ans;
  }
  }t;
  int main()
  {
  //  freopen("poj3171.in","r",stdin);
  scanf("%d%d%d",&n,&s,&e);
  for (int i=1;i<=n;i++) scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].S);
  sort(a+1,a+1+n);
  t.fillchar(e);
  t.insert(s-1,0);
  for (int i=1;i<=n;i++)
  {
  if (a[i].r<s) continue;
  t.insert(a[i].r,t.find(max(s-1,a[i].l-1),a[i].r-1)+a[i].S);
  }
  /*  for (int i=t.M;i<=t.M*2;i++) cout《t.t[i]《' ';
  cout《endl;
  */  if (t.t[e+2+t.M]==INF) cout《"-1\n";
  else cout《t.t[e+2+t.M]《endl;
  return 0;
  }

      

首页 上一页 1 2 下一页 尾页 2/2/2
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
分享到: 
上一篇单例模式---不仅仅是单例 下一篇HDU 1852 快速求幂

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容: