Codeforces #343 Div2. D. Babaei and Birthday Cake

円柱にする理由はストーリー設定以外にないね。
http://codeforces.com/contest/629/problem/D

問題

N個の円柱がある。
i番の円柱は底辺の半径がR[i]、高さがH[i]である。

これらの円柱をテーブルの上に縦に積み重ねたい。
以下の条件を満たすように積み重ねるとき、総体積の最大値を求めよ。

• 各円柱は積み重ねてもよいし積み重ねなくても良い。
• 上に乗る円柱は、下の円柱より大きな番号でなければならない。
• 上に乗る円柱は、下の円柱より大きな体積でなければならない。

解法

Range Maximum Queryを求められるデータ構造を用いて解く。
まず各円柱の体積を求め、小さい順に処理しよう。

i番の円柱の重ね方を考えるとき、1～(i-1)番の円柱それぞれを最上位とする円柱群のうち、総体積の最大となるものの上に載せていこう。
体積の小さい順に処理するので、番号が小さくでも体積の大きな円柱j番は、i番を処理する段階でまだ処理がなされておらず総体積は0なので、選ばれることはない。

template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	static V const def=0;
	V comp(V l,V r){ return max(l,r);};
	
	SegTree_1(){val=vector<V>(NV*2,def);};
	V getval(int x,int y,int l=0,int r=NV,int k=1) {
		if(r<=x || y<=l) return def;
		if(x<=l && r<=y) return val[k];
		return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	void update(int entry, V v) {
		entry += NV;
		val[entry]=v;
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};

int N;
ll R[101010],H[101010],V[101010],S[101010];
SegTree_1<ll,1<<20> st;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	vector<pair<ll,int>> P;
	cin>>N;
	FOR(i,N) {
		cin>>R[i]>>H[i];
		V[i]=R[i]*R[i]*H[i];
		
		P.push_back({V[i],-i});
	}
	sort(ALL(P));
	FORR(r,P) {
		i=-r.second;
		S[i]=V[i] + st.getval(0,i);
		st.update(i,S[i]);
	}
	ll v=st.getval(0,N);
	_P("%.12lf\n",v*atan(1)*4);
	
}

まとめ

パッと見SRMの帽子を重ねる問題みたいなのかと思ったら、もっと単純な問題だった。