Vexoben
May 25, 2018
题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=4007
题意
给定一棵n层的完全二叉树，要将每个节点涂为黑色或者白色。如果叶节点i和他的祖先j同为黑色，产生U(i,j)的贡献，同为白色产生V(i,j)的贡献，求黑色叶子节点不超过m个时这棵树的最大权值。
n<=10
题解
一开始想到最小割，但是不会处理黑色叶子不超过m个这个限制。
那么考虑DP，用f[i][j]表示以i为根的子树中，选了j个黑色叶子节点的最大权值。
但是按照正常的树形DP，会发现由于不知道叶节点选择的状态而很难转移。
如果我们已经知道了从根到节点x的路径上的点选黑还是白，那么节点x的左右孩子之间是独立的。枚举x的颜色，分别处理两个孩子，向上合并，这个复杂度是T(n)=4T(n/2)+O(n^2)。如果x是叶子节点，我们可以直接计算出他对于祖先的贡献。两个节点合并时，由于父亲节点的贡献被叶节点计算过，只需要直接用这两个节点的f向上转移即可。
可以算出复杂度是O(2^(2n)*n^2)
#include<bits/stdc++.h>
using namespace std;
const int N=1030;
int n,m,t[N],u[N][12],v[N][12],f[N][N];
void dfs(int x,int num) {
for (int i=0;i<=num;i++) f[x][i]=0;
if (num==1) {
for (int i=1;i<n;i++) {
if (t[x>>i]) f[x][1]+=u[x][i];
else f[x][0]+=v[x][i];
}
return;
}
t[x]=0; dfs(x<<1,num>>1); dfs(x<<1|1,num>>1);
for (int i=0;i<<1<=num;i++)
for (int j=0;j<<1<=num;j++)
f[x][i+j]=max(f[x][i+j],f[x<<1][i]+f[x<<1|1][j]);
t[x]=1; dfs(x<<1,num>>1); dfs(x<<1|1,num>>1);
for (int i=0;i<<1<=num;i++)
for (int j=0;j<<1<=num;j++)
f[x][i+j]=max(f[x][i+j],f[x<<1][i]+f[x<<1|1][j]);
}
int main() {
scanf("%d%d",&n,&m);
for (int i=0;i<1<<n-1;i++)
for (int j=1;j<n;j++)
scanf("%d",&u[i+(1<<n-1)][j]);
for (int i=0;i<1<<n-1;i++)
for (int j=1;j<n;j++)
scanf("%d",&v[i+(1<<n-1)][j]);
dfs(1,1<<n-1);
int ans=0;
for (int i=0;i<=m;i++) ans=max(ans,f[1][i]);
printf("%d",ans);
return 0;
}