Codeforces #279 Div2 F. Treeland Tour

本番大ざっぱな回答でTLEした。
http://codeforces.com/contest/490/problem/F

問題

N頂点からなる木を成すグラフが与えられる。
各頂点は町を表しており、各町の人口R[i]が与えられる。

ここで、ある町からある町に最短路を移動する。
その際、通過する町で音楽の演奏を行うことができる。
ただし、２回目以降の演奏は前の町の人口より多い町でしか演奏できない。

うまく移動開始・終了位置及び演奏位置を定め、演奏回数の最大値を求めよ。

解法

移動経路が先に定まってしまえば、あとは人口に対しLIS(Longest Increasing Subsequence)を求めるだけである。

開始位置を総当たりし、DFSで探索しながらLISを求めていけば良い。
DFSするので、LISを管理する配列の中身を更新した後に子頂点を探索したあと、配列の中身をもとに戻してから関数を抜けるようにすると良い。

int N;
int R[10005];
vector<int> E[60001];
int ma;
vector<int> V;

void dfs(int cur,int pre) {
	int pos,i,p;
	
	pos=lower_bound(V.begin(),V.end(),R[cur])-V.begin();
	
	if(pos==V.size()) p=-1, V.push_back(R[cur]);
	else p=V[pos], V[pos]=R[cur];
	ma=max(ma,(int)V.size());
	
	FOR(i,E[cur].size()) {
		int tar=E[cur][i];
		if(tar==pre) continue;
		dfs(tar,cur);
	}
	
	if(p==-1) V.pop_back();
	else V[pos]=p;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>R[i];
	FOR(i,N-1) {
		cin>>x>>y;
		x--,y--;
		E[x].push_back(y);
		E[y].push_back(x);
	}
	
	FOR(i,N) dfs(i,-1);
	cout<<ma<<endl;
	
}

まとめ

計算量をまじめに見積もらず適当に出してTLEしたので反省。