自动搬运

查看原文

来自洛谷，原作者为

	nosta 星空の下はダンスホール

搬运于2025-08-24 22:04:46，当前版本为作者最后更新于2019-03-22 20:41:38，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

【题意】定义有根树上一个结点的权值等于整个子树内的节点权值和，现给出$n(n\le15)$个节点的权值$\{w_n\}$，限制每棵树高度不超过$2$，求满足要求的带权森林个数。

【做法】考虑状压dp，设$f[i,j]$为按$w$排序小大排序后前$i$个节点所构成的森林中，高度为$1$的树集合为$j$的方案数，转移有

$$f[i,j]\to f[i+1,j+\{i+1\}]$$ $$f[i,j]\to f[i+1,j-k] \; (k\subseteq j,k\not=\varnothing,w_{i+1}=\sum_{e\in k}w_e) $$

即考虑让$i+1$作为高度为$1$或$2$的树的树根。注意到当$|k|=1$时，存在让$i+1$作为$k$中唯一点$e_0$的儿子的方案。显然仅当$w_i$单调不降时能取到所有决策。

【复杂度的推导】

$$\sum_{i=0}^{2^n-1}2^{\mathbb{popcount}_i} =\sum_{i=0}^n(n,i)2^i=\sum_{i=0}^n(n,i)1^{n-i}2^i=(1+2)^n=3^n $$

总时间复杂度为$O(n3^n)$，需要剪枝。

#include <bits/stdc++.h>
using namespace std;

const int mod=1e9+7;

int n,w[15],sum[1<<15];
int lmt,f[16][1<<15];

inline int lbt(int x) {return x&-x;}
inline void add(int&x,int y) {if((x+=y)>=mod) x-=mod;}

int main() {
	scanf("%d",&n);
	for(int i=0; i<n; ++i) scanf("%d",w+i); sort(w,w+n);
	for(int i=0; i<n; ++i) sum[1<<i]=w[i]; lmt=1<<n;
	for(int i=0; i<lmt; ++i) {
		if(i!=lbt(i)) sum[i]=sum[i-lbt(i)]+sum[lbt(i)];
	}
	f[0][0]=1;
	for(int i=0; i<n; ++i) {
		for(int j=0; j<lmt; ++j) if(f[i][j]) {
			add(f[i+1][j|(1<<i)],f[i][j]);
			for(int k=j; k; k=(k-1)&j) if(w[i]==sum[k]) {
				add(f[i+1][j^k],f[i][j]);
				if(k==lbt(k)) add(f[i+1][j^k],f[i][j]);
			}
		}
	}
	int ans=0;
	for(int i=0; i<lmt; ++i) {
		add(ans,f[n][i]);
	}
	printf("%d\n",ans);
	return 0;
}