【bzoj4007】[JLOI2015]战争调度 暴力+树形背包dp

题目描述

给你一棵 $n$ 层的完全二叉树，每个节点可以染黑白两种颜色。对于每个叶子节点及其某个祖先节点，如果它们均为黑色则有一个贡献值，如果均为白色则有另一个贡献值。要求黑色的叶子节点数目不超过 $m$ ，求最大总贡献值。

$n\le 10$

输入

第一行两个数 n;m。接下来 2^(n-1) 行，每行n-1 个数，第 i 行表示编号为 2^(n-1)-1+ i 的平民对其n-1直系上司的作战贡献度，其中第一个数表示对第一级直系上司，即编号为 (2^(n-1)-1+ i)/2 的贵族的作战贡献度 wij，依次往上。接下来 2^(n-1)行，每行n-1个数，第i行表示编号为 2^(n-1)-1+ i的平民对其n-1个直系上司的后勤贡献度，其中第一个数表示对第一级直系上司，即编号为 (2^(n-1)-1+ i)/2 的贵族的后勤贡献度 fij ，依次往上。

输出

一行一个数表示满足条件的最大贡献值

样例输入

3 4
503 1082
1271 369
303 1135
749 1289
100 54
837 826
947 699
216 389

样例输出

6701

题解

暴力+树形背包dp

[NOI2006]网络收费 的套路。

提前计算叶子节点的总贡献，设 $f[i][j]$ 表示以 $i$ 为根的子树中，$j$ 个叶子节点的颜色为黑色（ $j$ 个平民选择战争）的最大总贡献值。

那么这显然是一个树形背包问题，处理左右节点后背包合并即可。

但是由于叶子节点的贡献与其祖先节点的颜色选择有关，我们不能直接得到贡献。由于这是一棵完全二叉树，因此可以暴力枚举每个非叶子节点的颜色。

这样有递归式 $T(1)=O(\log k),T(k)=4T(\frac k2)+O(k^2)$ ，不考虑 $T(1)$ 时根据主定理解得 $T(k)=O(k^2\log k)$ ，考虑 $T(1)$ 时 $T(1)$ 被计算了 $k^2$ 次，贡献为 $O(k^2\log k)$ 。

因此总的时间复杂度是正确的，为 $O(2^{2n}·n)$ 。

#include <cstdio>
#include <algorithm>
#define N 1030
using namespace std;
int n , w[N][12] , v[N][12] , f[N][N] , p[12];
void dfs(int x , int d)
{
	int i , j;
	for(i = 0 ; i <= 1 << d ; i ++ ) f[x][i] = 0;
	if(!d)
	{
		for(i = 1 ; i <= n ; i ++ )
		{
			if(p[i]) f[x][1] += w[x][i];
			else f[x][0] += v[x][i];
		}
		return;
	}
	p[d] = 0 , dfs(x << 1 , d - 1) , dfs(x << 1 | 1 , d - 1);
	for(i = 0 ; i <= 1 << (d - 1) ; i ++ )
		for(j = 0 ; j <= 1 << (d - 1) ; j ++ )
			f[x][i + j] = max(f[x][i + j] , f[x << 1][i] + f[x << 1 | 1][j]);
	p[d] = 1 , dfs(x << 1 , d - 1) , dfs(x << 1 | 1 , d - 1);
	for(i = 0 ; i <= 1 << (d - 1) ; i ++ )
		for(j = 0 ; j <= 1 << (d - 1) ; j ++ )
			f[x][i + j] = max(f[x][i + j] , f[x << 1][i] + f[x << 1 | 1][j]);
}
int main()
{
	int m , i , j , ans = 0;
	scanf("%d%d" , &n , &m) , n -- ;
	for(i = 0 ; i < (1 << n) ; i ++ ) for(j = 1 ; j <= n ; j ++ ) scanf("%d" , &w[i + (1 << n)][j]);
	for(i = 0 ; i < (1 << n) ; i ++ ) for(j = 1 ; j <= n ; j ++ ) scanf("%d" , &v[i + (1 << n)][j]);
	dfs(1 , n);
	for(i = 0 ; i <= m ; i ++ ) ans = max(ans , f[1][i]);
	printf("%d\n" , ans);
	return 0;
}