【BZOJ1495】网络收费（NOI2006）-树形DP+状压DP

测试地址：网络收费
做法：本题需要用到树形DP+状压DP。
因为成对的贡献比较难做，我们尝试把贡献算到每一个叶子节点上。我们发现按照题目中的收费方式，它等价于对于每棵子树，A和B哪个更少，就统计这样的贡献：对于每个这种用户 $i$ ，如果 $i, j$ 的LCA是当前子树的根，则累计 $F (i, j)$ 。为什么等价呢？因为观察计费形式，假设A更少，那么对所有满足LCA为当前根的点对 $(i, j)$ ，如果两个同为A，则累计两次 $F (i, j)$ ，等价于累计 $F (i, j)$ 和 $F (j, i)$ 各一次，如果其中有一个为A，那么要么累计 $F (i, j)$ ，要么累计 $F (j, i)$ ，因此两种计算方式是等价的。注意到满足条件的 $j$ 一定是一个连续区间，因此我们可以预处理出前缀和，加快询问的速度。
接下来就要考虑状态转移了。我们发现在每个点上实际上是在做这样的决策：要使A更多还是使B更多。而我们发现，一个点的贡献受且仅受它的祖先决策的影响。注意到深度只有 $n$ ，所以我们可以在状态中开一维表示该点祖先的决策状态，最多有 $2^{n}$ 种。那么我们可以得到一个状态定义，如下：
令 $f (i, j, k)$ 为以点 $i$ 为根的子树中，点 $i$ 的祖先的决策状态为 $j$ ，子树中有 $k$ 个A时，能得出的最小花费。
当点 $i$ 为叶子节点时，我们可以借助前缀和 $O (n)$ 算出这个状态的花费，而其他点的状态就类似背包一样转移即可，可以证明时间复杂度为 $O (2^{2 n})$ 。
还有一点要注意，直接开 $f (i, j, k)$ 的话，空间复杂度为 $O (2^{3 n})$ ，无法接受，注意到在深度为 $d e p$ 时， $j$ 最多有 $2^{d e p}$ 种决策，而 $k$ 最大为 $2^{n - d e p}$ ，那么如果我们把这两维合并成一维，那么这一维从始至终最多有 $2^{n}$ 种组合，那么我们就把空间复杂度也优化到了 $O (2^{2 n})$ ，可以通过此题。
以下是本人代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf=1000000000ll*1000000000ll;
int n,p;
ll c[1050],sum[1050][1050],f[2050][2050];
bool type[1050];

ll calc(int v,int i,bool type)
{
    int x=1,l=1,r=(1<<n),dep=n-1;
    ll ans=0;
    while(l!=r)
    {
        int mid=(l+r)>>1;
        if (v<=mid)
        {
            if (!type^(i&(1<<dep)?1:0)) ans+=sum[v][r]-sum[v][mid];
            r=mid;
        }
        else
        {
            if (!type^(i&(1<<dep)?1:0)) ans+=sum[v][mid]-sum[v][l-1];
            l=mid+1;
        }
        dep--;
    }
    return ans;
}

void dp(int v,int dep)
{
    if (!dep)
    {
        for(int i=0;i<(1<<n);i++)
        {
            f[v][i*(1<<(dep+1))+0]=calc(v-(1<<n)+1,i,1);
            f[v][i*(1<<(dep+1))+1]=calc(v-(1<<n)+1,i,0);
            f[v][i*(1<<(dep+1))+type[v-(1<<n)+1]]+=c[v-(1<<n)+1];
        }
        return;
    }
    dp(v<<1,dep-1);
    dp(v<<1|1,dep-1);
    for(int i=0;i<(1<<(n-dep));i++)
        for(int j=0;j<=(1<<dep);j++)
        {
            int nxt=i*(1<<(dep+1))+j;
            f[v][nxt]=inf;
            bool flag=(j>=(1<<dep)-j);
            int nxtp=i*(1<<(dep+1))+flag*(1<<dep);
            for(int k=0;k<=j;k++)
                if (k<=(1<<(dep-1))&&j-k<=(1<<(dep-1)))
                    f[v][nxt]=min(f[v][nxt],f[v<<1][nxtp+k]+f[v<<1|1][nxtp+(j-k)]);
        }
}

void init()
{
    scanf("%d",&n);
    int p=(1<<(n+1))-1;
    for(int i=1;i<=(1<<n);i++)
        scanf("%d",&type[i]);
    for(int i=1;i<=(1<<n);i++)
        scanf("%lld",&c[i]);
    for(int i=1;i<=(1<<n);i++)
    {
        sum[i][i]=0;
        for(int j=i+1;j<=(1<<n);j++)
        {
            scanf("%lld",&sum[i][j]);
            sum[j][i]=sum[i][j];
        }
    }
    for(int i=1;i<=(1<<n);i++)
    {
        sum[i][0]=0;
        for(int j=1;j<=(1<<n);j++)
            sum[i][j]=sum[i][j-1]+sum[i][j];
    }
}

int main()
{
    init();
    dp(1,n);
    ll ans=inf;
    for(int i=0;i<=(1<<n);i++)
        ans=min(ans,f[1][i]);
    printf("%lld",ans);

    return 0;
}