BZOJ 1495 [NOI2006]网络收费（暴力DP）

题意

给定一棵满二叉树，每个叶节点有一个状态$0/1$，对于每两个叶节点$i,j$，如果这两个叶节点状态相同但他们的$LCA$所管辖的子树中的与他们状态相同的叶节点个数较少（少于$1/2$），则会产生$2f_{ij}$的代价，如果状态不同，则产生$f_{ij}$的代价，如果状态相同且$LCA$管辖子树中与他们状态相同叶节点个数较多，则不产生代价，现在每个节点可以变更状态，但变更状态也有自己的代价，求最小总代价 。

题解

在满二叉树上暴力枚举这个点子树中是$0$多还是$1$多，然后递归下去$DP$合并。时间复杂度是$O(2^ncdot 2^ncdot n)$的。对于每一个叶子结点，到根的路径最长只有$n$，所有情况就是$2^n$，所以所有叶子节点加起来的时间复杂度是$2^ncdot 2^n$，由于还要枚举这条路径上的点算代价，所以就再乘个$n$。

费用的计算方法就是：
对于点对$(i,j)$的贡献，如果$LCA$和$i$异色，费用就加上一个$f_{ij}$，如果$LCA$和$j$异色，就再加上一个$f_{ij}$。可以发现这样算出来的答案恰好符合题意。$LCA$的颜色就表示子树下面$1$多还是$0$多，这个是暴力枚举的。

具体实现看代码。

CODE

$dp[i][j]$表示在$i$的子树里选了$j$个$1$的最小费用。

#pragma GCC optimize (3)
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN = 2060;
const LL INF = 1ll<<40;
int f[MAXN][2], n, all, a[MAXN];
LL dp[MAXN][MAXN], cst[MAXN][12];
bool clr[12];
void dfs(int x, int dep) {
	for(int i = 0; i <= all; ++i) dp[x][i] = INF;
	if(dep == n) {
		dp[x][0] = f[x-all][0];
		dp[x][1] = f[x-all][1];
		for(int i = 0; i < n; ++i) dp[x][clr[i]^1] += cst[x-all][i];
		return;
	}
	int half = 1<<(n-dep-1);
	clr[dep] = 0; dfs(x<<1, dep+1), dfs(x<<1|1, dep+1);
	for(int i = 0; i <= half; ++i)
		for(int j = 0; i+j <= half; ++j)
			dp[x][i+j] = min(dp[x][i+j], dp[x<<1][i] + dp[x<<1|1][j]);
	
	clr[dep] = 1; dfs(x<<1, dep+1), dfs(x<<1|1, dep+1);
	for(int i = 0; i <= half; ++i)
		for(int j = half+1-i; j <= half; ++j)
			dp[x][i+j] = min(dp[x][i+j], dp[x<<1][i] + dp[x<<1|1][j]);
}
int lca_dep(int u, int v) {
	for(int i = n-1; i >= 0; --i) if((u>>i) != (v>>i)) return n-i-1;
}
int main () {
	scanf("%d", &n); all = 1<<n;
	for(int i = 0; i < all; ++i) scanf("%d", &a[i]);
	for(int i = 0; i < all; ++i) f[i][a[i]] = 0, scanf("%d", &f[i][a[i]^1]);
	for(int i = 0; i < all; ++i)
		for(int j = i+1; j < all; ++j) {
			int k = lca_dep(i, j), v; scanf("%d", &v);
			cst[i][k] += v, cst[j][k] += v;
		}
	dfs(1, 0);
	printf("%lld
", *min_element(dp[1], dp[1] + all + 1));
}