【题解】[NOI2006] 网络收费 树形 DP —Qiuly

$40\ pts$

完全是送的。

直接枚举需要修改的集合然后算贡献，复杂度大概是 $O(2^{2^n})$ 级别。

$100\ pts$

发现自己好蠢啊……

设 $f_{i,j}$ 表示树上第 $i$ 个点其子树下的叶子节点中有 $j$ 个 $\rm{B}$ 类结点，其他的全部是 $\rm{A}$ 类结点时，关于这棵子树的最小费用。

转移如下：
$$
f_{i,j}=\min{f_{lson_i,x}+f_{rson_i,y}\ \ [x+y=j]}
$$
考虑初始化，如果当前点是叶子节点的话，对于一个其他的叶子节点 $j$ ，它们所产生的 $f_{i,j}$ 的贡献只会在 $lca_{i,j}$ 上计算。

现在给 $lca$ 也赋一个值，如果 $nA<nB$ 值为 $B$ ，否则为 $A$ 。这样 $i,j$ 两点的贡献便可以分开来算。如果 $i$ 和 $lca_{i,j}$ 的值不同，那么 $lca_{i,j}$ 的费用将加上一个 $f_{i,j}$ ，同时 $j$ 也一样。

那么赋初值也搞定了，代码：

if(dep==n) {/*当 x 已经是叶子节点时*/
    dp[x][0]=C[x-m][0],
    dp[x][1]=C[x-m][1];
    /*C[x][0] 就是点 x 选择 0 付费方式时需支付的额外费用*/
    /*就像题目中给定的转换费用*/
    for(int i=dep;i>=0;--i) dp[x][vis[i]^1]+=f[x-m][i];
    /*输入的时候就将所有的贡献记到 lca 上，这个时候用就好*/
    /*i 是按照深度枚举祖先，vis[i] 是当前的祖先钦定的值 (0/1)*/
    return;
}

树形 $\rm{DP}$ ，$dfs$ 的时候对于一个点 $x$ ，我们钦定其的值为 $A$ 或者是 $B$ ，转移的时候对 $x+y$ 的大小判断一下即可。

Code:

#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N=1024+5;
int n,m,vis[N],t[N];
ll C[N][2],f[N][N],dp[N][N];

template <typename _Tp> inline void IN(_Tp&x) {
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    if(flag) x=-x;
}

inline int lca(int x,int y) {
    for(int i=n-1;i>=0;--i)
        if((x>>i)^(y>>i)) return n-i-1;
}
void dfs(int x,int dep,int l,int r) {
    if(dep==n) {
        dp[x][0]=C[x-m][0],dp[x][1]=C[x-m][1];
        for(int i=dep;i>=0;--i) dp[x][vis[i]^1]+=f[x-m][i];
        return;
    }
    memset(dp[x],0x3f,sizeof(dp[x]));
    int mid=(l+r)>>1;
    vis[dep]=0;
    dfs(x<<1,dep+1,l,mid),dfs(x<<1|1,dep+1,mid+1,r);
    for(int i=0;i<=mid-l+1;++i)
        for(int j=0;j<=r-mid&&i+j<=r-l+1;++j)
            if(i+j<=r-l+1-i-j) dp[x][i+j]=min(dp[x][i+j],dp[x<<1][i]+dp[x<<1|1][j]);
    /*上面的 if 就是确保当前值下计算的答案符合要求*/
    vis[dep]=1;
    dfs(x<<1,dep+1,l,mid),dfs(x<<1|1,dep+1,mid+1,r);
    for(int i=0;i<=mid-l+1;++i)
        for(int j=0;j<=r-mid&&i+j<=r-l+1;++j)
            if(i+j>r-l+1-i-j) dp[x][i+j]=min(dp[x][i+j],dp[x<<1][i]+dp[x<<1|1][j]);
}

int main() {
    IN(n),m=1<<n;
    for(int i=0;i<m;++i) IN(t[i]);
    for(int i=0;i<m;++i) IN(C[i][t[i]^1]);
    for(int i=0;i<m;++i) 
        for(int j=i+1,v;j<m;++j)
            IN(v),f[i][lca(i,j)]+=v,f[j][lca(i,j)]+=v;
    dfs(1,0,1,m);
    ll ans=1e18+2;
    for(int i=0;i<=m;++i) ans=min(ans,dp[1][i]);
    printf("%lld\n",ans);
    return 0;
}