yukicoder : No.417 チューリップバブル

なんでこんなストーリーにしたんだろう？
http://yukicoder.me/problems/no/417

問題

根付き木を成す無向グラフが与えられる。
各辺には移動時間、各頂点iにはスコアU[i]が割り振られる。

根の頂点からいくつかの頂点を辿り、根に戻る移動経路を考える。
総移動時間がM以下で到達可能な頂点のスコアの総和の最大値を求めよ。

解法

各頂点に対し、そのサブツリー内で限られた時間内で最大どれだけスコアを稼げるか考えよう。

f(v,t) := 頂点vのサブツリー内で、頂点vから始まり頂点vに戻る移動経路において時刻tであるものの到達頂点のスコアの総和の最大値
根頂点をuとするとf(u,*)の最大値が解である。

vの子頂点を一つも辿らない場合、f(v,*) = U[v]である。
以下、vの子頂点c毎に以下のDPで状態を更新しよう。v→cの移動距離をtとすると、v→cの移動とc→vの移動で計2*t時間がかかるので、
f(v,i) = max(f(v,i), f(v,i-(2*t+j)) + f(c,j))
の要領で更新していく。
同じ子頂点を複数回カウントしないよう、更新順は気を付けよう。

なお、各辺は常に往復するのでDP中で考えなければならない時刻は偶数だけである。
(別に奇数も考慮しても通るけど)

int N,M;
int U[1020];
ll dp[202][1020];
vector<pair<int,int>> E[202];

void dfs(int cur,int pre) {
	int i,j;
	FOR(i,M+1) dp[cur][i]=U[cur];
	
	FORR(e,E[cur]) if(e.first!=pre) {
		int tar=e.first;
		int cost=e.second;
		dfs(tar,cur);
		
		for(i=M;i>=0;i--)
			for(j=0;j+cost<=i;j++)
				dp[cur][i] = max(dp[cur][i],dp[cur][i-(j+cost)]+dp[tar][j]);
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	M/=2;
	FOR(i,N) cin>>U[i];
	FOR(i,N-1) {
		cin>>x>>y>>r;
		E[x].push_back({y,r});
		E[y].push_back({x,r});
	}
	dfs(0,-1);
	
	cout<<*max_element(dp[0],dp[0]+M+1)<<endl;
}

まとめ

割と典型？