Codeforces 429(#245 Div1) C. Guess the Tree

問題

n頂点からなる木で、各頂点以下の部分木のサイズがc[i]であるような木であり、
葉以外の頂点では直接の子が二つ以上のものが存在するか、
存在するならYESを、そうでないならNOを出力せよ。

制約条件

n≦24

方針

DP.
葉と内点を区別して考える。
内点の出次数は2以上なので、
|葉| = Σ|内点の出次数| - (|内点| - 1)
|内点| + |葉| ≧ |内点| * 2 + 1
23 / 2≧|内点|
より内点は11個以下。

dp[i][j]を、根がi個ある森で、使う内点の頂点の集合がjであるようなもののうち、
葉の個数の最小であるものにおける葉の個数とする。

これを更新するDPをして、根に足りない葉をつけられるかみればよい。
更新は、今までの森に一つ木を足すか、一つの頂点に森をくっつけて木にするかのどちらか。

ソースコード

int n, out;
vi in;

int dp[12][1 << 11];

bool check(){
	
	rep(i, n + 1) rep(j, 1 << n) dp[i][j] = inf;
	rep(i, n) if(in[i] >= 3) dp[1][1 << i] = in[i];
	
	rep(i, 1 << n){
		rep(j, n) for(int k = (i - 1) & i; k; k = (k - 1) & i){
			
			if(dp[j][k] < inf && dp[1][i ^ k] < inf)
				dp[j + 1][i] = min(dp[j + 1][i], dp[j][k] + dp[1][i ^ k]);
		}
		rep(j, n) if(!(i & 1 << j)) rep(k, n){
			
			if(in[j] - 1 < dp[k][i]) continue;
			if(in[j] - 1 - dp[k][i] + k < 2) continue;
			
			dp[1][i | 1 << j] = in[j];
		}
	}
	return dp[1][(1 << n) - 1] < inf && in[n - 1] == n + out;
}

int main(){
	cin >> n;
	rep(i, n){
		int x; cin >> x;
		if(x == 1) out++;
		else in.pb(x);
	}
	if(n == out || in.size() > 11){
		cout << (n == 1 ? "YES" : "NO") << endl;
		return 0;
	}
	
	sort(all(in));
	n = in.size();
	
	cout << (check() ? "YES" : "NO") << endl;
	
	return 0;
}