POJ-1694: An Old Stone Game

keyword

メモ化再帰　greedy　C++

問題概要

ノード数200以下の有向木が与えられる。以下のゲーム(一人用)をする。各ターン毎にプレイヤーは以下のいずれかの行動をとる。

• 葉に石をおく。
• 葉でないノードpに対して、全ての子(not 子孫)に石が置いてあるならば、その石を取り除きpに一つ石を置く。

根に石を置くために必要な石の最小数を求める問題。

解法

各ノードから、子に関して必要な石の個数を再帰的に求め、必要な石が多い順に実際に置いていけば良い。実装時間は20分くらい。

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int N;
vector<int> G[209];
int dp[209];

int rec(int x){
	if(G[x].empty()) return 1;
	if(dp[x]) return dp[x];
	vector<int> vs;
	for(int i=0; i<G[x].size(); i++){
		vs.push_back(rec(G[x][i]));
	}
	sort(vs.rbegin(), vs.rend());
	int ret = 1;
	for(int i=0; i<vs.size(); i++){
		ret = max(ret, vs[i] + i);
	}
	return dp[x] = ret;
}

int main(){
	int M;
	scanf("%d",&M);
	for(int i=0; i<M; i++){
		scanf("%d",&N);
		for(int j=0; j<N; j++) G[j].clear();
		for(int j=0; j<N; j++) dp[j] = 0;
		for(int j=0; j<N; j++){
			int p, x, a;
			scanf("%d%d",&p,&a);
			p--;
			for(int k=0; k<a; k++){
				scanf("%d",&x);
				x--;
				G[p].push_back(x);
			}
		}
		printf("%d\n",rec(0));
	}
	return 0;
}