Codeforces #282 Div1 C. Helping People

1750ptだけど、これ自力回答できたなぁ。
http://codeforces.com/contest/494/problem/C

問題

N人の人がおり、初期状態でそれぞれ所持金をA[i]ドルを持っている。

ここで、Q通りの寄付を行う。
各寄付jはL[j]、R[j]、P[j]で表現される。
その意味は確率P[j]で寄付が実行され、その際A[L[j]]～A[R[j]]の所持金が１ドル増える。

なお、各寄付の範囲L[j]、R[j]は交差しない。
寄付同士は重複しない範囲を対象とするか、片方の範囲がもう片方を完全に含む。

全寄付終了後、最大の所持金を持つ人の所持金の期待値を求めよ。

解法

寄付が交差しないことから、寄付の包含関係を木で表現できる。
よってまずそのような包含関係を作成する。
最初に、全範囲を含む確率0の寄付を追加しておくと、そこを根とする木が作れるので処理が楽になる。

後は寄付の範囲の小さい順にDPしていけばよい。
各寄付のDPではその範囲の所持金の最大値とその確率の対を計算する。

各寄付は、それより小さい範囲の寄付及び、小範囲の寄付に含まれないような人を含む。
まずより小範囲の寄付に含まれない人の所持金最大値を求める。
その最大値を、各小さい寄付における最大値と確率の対と比較して最大値を更新していく。
最後に、当該寄付は確率P[i]で最大値が1更新されるので、最大値の確率の対を変更していく。

int N,Q;
int A[100500];
int L[6000],R[6000];
double P[6000];
int par[5002];
vector<pair<int,int> > C[100020];
int ma[5002];
map<int,double> res[5002];

map<int,double> merge(map<int,double> m1,map<int,double> m2) {
	map<int,double> res;
	ITR(it1,m1) ITR(it2,m2) if(it1->second*it2->second)
		res[max(it1->first,it2->first)] += it1->second*it2->second;
	return res;
}

int dfs(int cur,int le) {
	int x=0;
	sort(ALL(C[cur]));
	ma[cur]=-1;
	
	for(;le<=R[cur];le++) {
		while(x<C[cur].size() && C[cur][x].first==le) le=dfs(C[cur][x].second,le), x++;
		if(le>R[cur]) break;
		ma[cur]=max(ma[cur],A[le]);
	}
	
	map<int,double> tmp;
	tmp[ma[cur]]=1.0;
	FOR(x,C[cur].size()) tmp=merge(tmp,res[C[cur][x].second]);
	ITR(it,tmp) {
		res[cur][it->first+1] += it->second*P[cur];
		res[cur][it->first] += it->second*(1-P[cur]);
	}
	return le;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	FOR(i,N) cin>>A[i];
	
	FOR(i,Q) cin>>L[i+1]>>R[i+1]>>P[i+1], L[i+1]--,R[i+1]--;
	Q++;
	L[0]=0,R[0]=N-1;
	
	FOR(i,Q) {
		par[i]=-1;
		int w=N+1;
		FOR(j,Q) if(i!=j) {
			if(L[j]==L[i]&&R[i]==R[j]) {
				if(j<i) par[i]=j, w=R[i]-L[i];
			}
			else if(L[j]<=L[i]&&R[i]<=R[j]&&R[j]-L[j]<=w) par[i]=j, w=R[j]-L[j];
		}
		if(par[i]!=-1) C[par[i]].push_back(make_pair(L[i],i));
	}
	
	dfs(0,0);
	double ret=0;
	ITR(it,res[0]) ret += it->first*it->second;
	_P("%.12lf\n",ret);
	
}

まとめ

寄付範囲が交差しないという条件で、木が作れることに気づくとすぐ。