Codeforces ECR #077 : E. Tournament

ECR6問回の5問目にしては優しいかも。
http://codeforces.com/contest/1260/problem/E

問題

N人(2の累乗)のトーナメントを考える。
各人の強さが与えられている。

うち一人、プレイヤーが勝たせたい参加者がいる。
プレイヤーが直接対戦する相手について、各相手が指定する金額を払えば強さを問わず勝ちにできる。
トーナメントの組み合わせは任意に指定できるとき、勝たせたい参加者を優勝されるための最少金額はいくらか。

解法

勝たせたい参加者よりもともと弱い参加者は金額0と考える。
N=2^Lとする。
とすると、勝たせたいプレイヤーが直接対戦するL人を選び、その金額の総和の最小値を求めよう。
ただ、i回戦で戦う相手は、事前に2^(i-1)-1人に勝っていなければならない。
よってその相手より弱い人を2^(i-1)-1人選ぶことにする。

こう考えると、弱い相手ほど上まで勝ち上がらせるのが難しいので、弱い相手ほど先に戦うことにする。
f(i,n) := i回戦で戦うのは強さが下からn番目の相手とするときの支払い最少金額
とすると、f(i+1,m) := f(i,n)+(強さが下からm番目に払う金額)と遷移できる。
ただし、この場合(i+1)回目までにm番目より弱い人が(2^i-2)人いなければならない。

int N,L;
int A[1<<18];
int X;
ll dp[19][1<<18];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	while(1<<L < N) L++;
	FOR(i,N) {
		cin>>A[i];
		if(A[i]==-1) X=i;
	}
	FOR(i,X+1) A[i]=0;
	
	FOR(j,L+1) FOR(i,N) dp[j][i]=1LL<<60;
	dp[0][N-1]=A[N-1];
	int num=1;
	for(i=1;i<=L;i++) {
		num+=1<<(L-i);
		ll mi=1LL<<60;
		for(j=N-1;j>=N-num;j--) {
			dp[i][j]=mi+A[j];
			mi=min(mi,dp[i-1][j]);
		}
	}
	cout<<dp[L][0]<<endl;
	
}

まとめ

落ち着いて考えれば簡単。