yukicoder : No.860 買い物

参加が遅れたので全完できず。
https://yukicoder.me/problems/no/860

問題

N個の商品を順に買う。
各商品には価格C[i]と梱包費用D[i]が設定されている。

商品はいくつか連続してまとめて買うことができ、L～R番目の商品をまとめて買う時にかかる費用は、sum(C[L...R])+sum(D[(L+1)...R])+min(C[L...R]) となる。
うまくまとめたとき、総費用の最小値はいくらか。

解法

まとめ買いすると、sum(C[L...R])+sum(D[L...R])に対し、最初の商品のD[L]が引かれて、min(C[L...R])が加算されることになる。
これを用いてDPで解くこともできる。
DPでは、D[L]が引かれたのち、これまでmin(C[L...R])を足してきたかどうかという状態別に、これまでの費用の総和の最小値を求めていくことになる。

Editorialの解法が実装量はともかく考え方がきれいなので、以下はそちらで解いた。
(N+1)頂点の無向グラフを考える。
0～(N-1)番の頂点は、N個の商品に対応する。
N番の頂点とi番の頂点を重みC[i]の辺でつなぎ、(i-1)番とi番の頂点(i＜N)を重みD[i]の辺でつなごう。

この無向グラフの最小全域木のコスト+sum(C[i])が解になる。
元々、0-N番の辺がつながっており、あと0～(N-1)番の頂点がそれぞれコストD[1]～D[N-1]の辺でつながれている状態を考える。
コストD[i]の辺を切ろうとすると、代わりに(i+1)番以降の頂点j番のいずれかをN番とつなぐため、コストC[j]の辺を使う、ということになる。
これを繰り返すことを考えると、最小全域木を求めるのと同じことになる。
　

int N;
vector<pair<ll,pair<int,int>>> E;

template<int um> class UF {
	public:
	vector<int> par,rank;
	UF() {rank=vector<int>(um,0); for(int i=0;i<um;i++) par.push_back(i);}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<500000> uf;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	ll S=0;
	FOR(i,N) {
		cin>>x>>y;
		S+=x;
		E.push_back({x,{N,i}});
		if(i) E.push_back({y,{i-1,i}});
	}
	sort(ALL(E));
	FORR(e,E) {
		x=e.second.first;
		y=e.second.second;
		
		if(uf[x]!=uf[y]) {
			uf(x,y);
			S+=e.first;
		}
	}
	
	cout<<S<<endl;
	
}

まとめ

Union-Find込だと、最小全域木解法は実装量さほど軽くはないんだけど、考え方のシンプルさがいいね。