ARC026-C 蛍光灯

問題

C - 蛍光灯

考察

貪欲ではできなそう

L<=10^5なので、dp[i]=i番目までの区間が全て照らされているときのコストの合計の最小値 というDPを考える

右端の座標をキーにソートしておくと、dp[r]=min(dp[r],min{dp[l],dp[l+1],...,dp[r-2],dp[r-1]}+c) というように遷移させられるが、これだとO(L^2)で間に合わない

[l,r)における最小値を高速に求めたい(いわゆるRMQ(Range Minimum Query))

SegmentTreeを使うことで各dp[r]についてO(logL)で求めることができ、全体の計算量はO(NlogL)なので間に合う

実装

自分が書いた時はソートをせずに各座標ごとにvectorに突っ込んだ

#include<bits/stdc++.h>
using namespace std;
#define all(vec) vec.begin(),vec.end()
typedef long long int ll;
typedef pair<ll,ll> P;
const ll MOD=1000000007;
const ll INF=1000000010;
const ll LINF=4000000000000000010LL;
const int MAX=310;
const double EPS=1e-3;
int dx[4]={0,1,0,1};
int dy[4]={0,0,1,1};
struct SegmentTree{
    int siz;
    vector<ll> node;
    SegmentTree(int n,ll init){
        siz=1;
        while(siz<n)siz<<=1;
        node.assign(2*siz,init);
    }

    void update(int k,ll x){
        k+=siz-1;
        node[k]=x;
        while(k>0){
            k=(k-1)/2;
            node[k]=min(node[2*k+1],node[2*k+2]);
        }
    }

    ll query(int a,int b,int k=0,int l=0,int r=-1){
        if(r<0)r=siz;
        if(r<=a||b<=l)return LINF;
        if(a<=l&&r<=b)return node[k];
        ll vl=query(a,b,2*k+1,l,(l+r)/2);
        ll vr=query(a,b,2*k+2,(l+r)/2,r);
        return min(vl,vr);
    }
};
vector<P>v[100010];
ll dp[100010];
int main(){
	int n,L;cin>>n>>L;
	for(int i=0;i<n;i++){
		int l,r,c;cin>>l>>r>>c;
		v[r].push_back(P(l,c));
	};
	fill(dp,dp+L+1,LINF);
	dp[0]=0;
	SegmentTree tree(L+2,LINF);
	tree.update(0,0);
	for(int i=1;i<=L;i++){
		for(auto p:v[i]){
			int l=p.first;
			ll c=p.second;
			ll mi=tree.query(l,i);
			dp[i]=min(dp[i],mi+c);
		}
		tree.update(i,dp[i]);
	}
	cout<<dp[L]<<endl;
    return 0;
}

感想

SegmentTreeをうまく使って高速化できたのは初めてなので嬉しい