VK Cup 2015 Round 3 : F. Quest

問題文の設定が難しい…？
http://codeforces.com/contest/542/problem/F

問題

N通りの問題があり、それぞれ解くのにかかる時間はt[i]、面白さはq[i]である。
これらの問題からいくつかを選び、選んだ問題が葉に1対1対応する二分木を作りたい。
この際、t[i]+(葉の頂点の深さ)==Tとなるように問題を葉に対応付けたい。

条件を満たす対応付けのうち、選んだ面白さの操作の最大値を求めよ。

解法

まず与えられた問題群を、配置可能な深さごとにまとめ、それぞれ面白さの降順ソートする。
あとはメモ化の要領で各深さに何個葉を置くかを探索していき、置く数が決まったら面白い順に配置していくと良い。

int N,T;
vector<int> Q[1010];

int memo[101][1001];

int dodo(int left,int node) {
	if(left==0 || node==0) return 0;
	node=min(node,1000);
	int i;
	int& ret=memo[left][node];
	if(ret>=0) return ret;
	ret = 0;
	
	int take,tot=0;
	for(i=0;i<=min(node,(int)Q[left].size());i++) {
		if(i) tot += Q[left][i-1];
		ret = max(ret,tot+dodo(left-1,2*(node-i)));
	}
	return ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>T;
	FOR(i,N) {
		cin>>x>>y;
		Q[x].push_back(y);
	}
	MINUS(memo);
	FOR(i,T+1) sort(ALL(Q[i])), reverse(ALL(Q[i]));
	
	cout<<dodo(T,1)<<endl;
}

まとめ

もうちょっとシンプルな問題文にしてもよさそうだったけど…。