吐槽：这道题真心坑...做了一整天，我太蒻了...

题意

构造一棵 $ n $ 个节点的树，要求满足以下条件：

• 每个非叶子节点至少包含2个儿子；
• 以节点 $ i $ 为根的子树中必须包含 $ c_i $ 个节点。

给出 $ n (n<=24)$ 和 $ c_i $ ，问是否存在符合条件的树。

分析

看到数据范围，第一时间想到的方法应该是状压DP，用数 $ s $ 表示已经被选入子树的点的集合，将两个以上小的子树合并为大的子树，看最后能否得到 $ s=1<<(n-1)-1 $ 这一集合。这么做的话，你就会…… 爆炸般地TLE

为什么？稍加分析就会发现，一共有 $ 2^n-1 $ 种状态，超过了 $ 1600 $ 万，其中绝大多数都是无法合并（有交集）的，遍历的时间大大超过了转移的时间。并且，题目问的是树是否存在，并不需要求出每一个状态，我们做了非常多的冗余操作。事实上，我们只需要找到一组解就可以了。那么，怎么快速确定某棵子树是否存在呢？

深搜+贪心。

我们发现，在确定比较大的子树时，我们总是需要用到小的子树，而大子树的存在性只与小子树的大小有关，与组合方式无关，所以我们可以dfs搜索子树的组合，并且一搜到解就退出。那么按照什么样的顺序搜索组合呢？可以直观地想到，在一开始放入的子树越大，越容易出解，所以我们在搜索每个子树的组合时按照从大到小的顺序搜，搜到解后删除原来的子树集合并用新的大子树代替以防止重复搜索，最后判断 $ 111...1 $ 这一集合是否存在。

另外，在读入 $ c_i $ 后按照大小排序，可以降低编程复杂度。

代码

AC,15ms，CF评测机真乃神机也

//by sclbgw7

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <vector>

#define R register

using namespace std;

int si[25];//保存子树大小

vector<int> dp[25];//dp[i]存放表示大小为i的子树的集合

int dfs(int s,int x,int y)

{

	if(x==0)

	{

		if(!b[s])

		  dp[si[y]].push_back(s),b[s]=1;

		return 1;

	}

	if(s)//如果已经选择了一些小子树

	{

		for(int i=x;i>=1;--i)

		  for(int j=dp[i].size()-1;j>=0;--j)

		    if(!(s&dp[i][j]))

		      if(dfs(s|dp[i][j],x-i,y))

		        {dp[i].pop_back();return 1;}

		return 0;

	}

	s=(1<<(y-1));

	for(int i=x-2;i>=1;--i)//内部节点必须有两个以上的儿子

	  for(int j=dp[i].size()-1;j>=0;--j)

	    if(!(s&dp[i][j]))

	      if(dfs(s|dp[i][j],x-i-1,y))

	        {dp[i].pop_back();return 1;}

	return 0;

}

int main()

{

	int n,m;

	scanf("%d",&n);

	for(int i=1;i<=n;++i)

	  scanf("%d",&si[i]);

	sort(si+1,si+1+n);

	int i;

	for(i=1;si[i]==1;++i)

	  dp[1].push_back(1<<(i-1));

	for(;i<=n;++i)

	  dfs(0,si[i],i);

	if(dp[n].size())

	  printf("YES\n");

	else

	  printf("NO\n");

	return 0;

}