ライブラリのグダグダがなかった分、Cよりこちらの方が楽だった。
http://k4pc.contest.atcoder.jp/tasks/k4pc_d
問題
運動会においてN個の競技がある。
各競技はA[i]~B[i]の時間にわたり開催され、参加すると満足度F[i]を得る。
時間の重複する競技への多重参加や、1競技に部分的に参加することはできない。
なお、運動会に参加している間、競技参加の有無を問わず時間1につき満足度がC減少する。
運動会には任意のタイミングで参加・退場可能だが、1回退場すると再参加はできない。
運動会の参加タイミングと、参加する競技を最適化したとき、得られる最大の満足度を答えよ。
解法
競技を終了時刻B[i]順にソートし、処理していく。
これまでの競技における(競技の終了時刻, そこまでの合計満足度)を配列にしまい管理する。
各競技に参加した場合、配列中からA[i]以前で最もA[i]に近い(競技の終了時刻, そこまでの合計満足度)をlower_bound等で求め、そこまでの満足度に(F[i] - C*(B[i]-前の競技の終了時刻))を足したものがこの競技終了時の最大満足度である。
よって(B[i], そこまでの満足度 + F[i] - C*(B[i]-前の競技の終了時刻))を配列に足していく。
終了時刻順に処理するので、配列の中身における時刻は昇順になる。
その際、最大満足度を得るのに最適でない競技があればそれを外しておく。
例えば配列中に(tx, sx)、(ty, sy)という2要素があるとする。
tx<tyとすると、sy < sx - C*(ty-tx)だったら、tyに終わる競技に参加する意味はないので、配列から外す。
ll N,C; ll A[100020],B[100020],F[100020]; pair<ll,int> P[1000050]; ll ma=0; vector<pair<ll,ll> > V; void solve() { int i,j,k,l,r,y; string s; cin>>N>>C; FOR(i,N) { cin>>A[i]>>B[i]>>F[i]; P[i]=make_pair(B[i],i); } V.push_back(make_pair(0,0)); sort(P,P+N); FOR(j,N) { i=P[j].second; ll x=F[i]-C*(B[i]-A[i]); // first vector<pair<ll,ll> >::iterator it=lower_bound(V.begin(),V.end(),make_pair(A[i]+1,0LL)); it--; x=max(x,it->second + F[i] - C*(B[i]-it->first)); while(V.size() && V.back().first==B[i] && V.back().second<x) V.pop_back(); int ng=0; if(V.size() && V.back().second-C*(B[i]-V.back().first)>=x) ng=1; if(ng==0) V.push_back(make_pair(B[i],x)); ma=max(ma,x); } cout<<ma<<endl; }
まとめ
最適手のリストをキュー風に管理する問題、しばしば出るね。