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; }