土下座しながら探索中

主に競技プログラミング

UVa 11908 : Skyscrapper

問題リンク : http://uva.onlinejudge.org/external/119/11908.pdf

問題概要 :
いくつかの重み付きの線分が与えられる
それらの内いくつかを選択し、その重みの総和を最大化せよ
ただし、ある点が複数の線分におおわれてはならない

解法 :
重み付き区間スケジューリングそのままなのでlower_boundつかってDPする

コード :

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

struct Segment {
  int s,t,weight;
  bool operator < (const Segment &seg) const {
    if( t != seg.t ) return t < seg.t;
    if( s != seg.s ) return s < seg.s;
    return weight < seg.weight;
  }
};

const int MAX = 1000000;
int dp[MAX];
int N; //ノード数

int Scheduling(vector<Segment> &segs){
  sort(segs.begin(),segs.end());
  vector<int> buf;
  rep(i,(int)segs.size()){
    int prev = lower_bound(buf.begin(),buf.end(),segs[i].s) - buf.begin();
    --prev;
    dp[i] = max((i?dp[i-1]:0),segs[i].weight+((prev==-1)?0:dp[prev]));
    buf.push_back(segs[i].t);
  }
  return dp[(int)segs.size()-1];
}

int main(){
  int T,CNT= 1;
  scanf("%d",&T);
  while( T-- ){
    scanf("%d",&N);
    vector<int> vec;
    vector<Segment> segs;
    rep(i,N) {
      int s,t,c;
      scanf("%d %d %d",&s,&t,&c);
      t = s + t-1;
      vec.push_back(s);
      vec.push_back(t);
      segs.push_back((Segment){s,t,c});
    }
    printf("Case %d: %d\n",CNT++,Scheduling(segs));
  }
  return 0;
}