「NOI2006」网络收费

题目链接

神仙题Orz

一开始以为是个最小割结果发现不太可做，这题的压缩祖先状态的方法真的神。

我们发现点对的贡献不是很好计算，所以我们考虑计算点的贡献。我们发现本质上付费系数只与 $i$ 和 $j$ 分别与lca的关系有关，也就是这条链的贡献可以转化为两个点对lca的贡献，即链的贡献与 $i$ 和 $j$ 的关系无关。具体贡献看下面。

首先，我们计算一个数组 $s[i][j]$，它的值为 $\sum\limits_{k,lca(i,k)=j}F_{i,k}$ （$i$ 是叶子），我们可以通过枚举点对求出这个数组。那么某一种方案的费用我们就可以用 $s$ 的和来表示。我们现在给非叶子节点也定义状态：对于这个节点的子树，当 $n_A\geqslant n_B$ 时为状态A，当 $n_A<n_B$ 时为状态 B。那么我们观察收费表可知，当 $i$ 和 $j$ 状态不同（$i$ 是叶子，$j$ 是 $i$ 的祖先）时，$s[i][j]$ 的贡献系数为 $1$，状态相同时为 $0$。举个例子，如果现在 $n_A<n_B$ 而且 $i$ 选择的付费方式为 $A$ ，那么 $s[i][j]$ 对答案造成的贡献就是 $s[i][j]$ ，如果是 $B$ ，那么贡献就是 $0$。如果我们知道了所有点的状态，对每个点和它的所有祖先都这么算一遍，我们就会不重不漏地计算出所有链的贡献（贡献系数为2就是在两个端点处都计算了一次）。

但是如果你直接暴力枚举状态和最朴素的暴力没有区别，我们这么计算贡献是为了方便dp。我们设 $f[i][j][k]$ 为当前dfs到节点 $i$ ，它的子树内共有 $j$ 个选了 $B$ 的叶子节点，它到根节点路径上每个点的状态为 $k$ 。那么当我们dfs到叶子节点时，所有祖先的状态都已知，我们把 $\sum s[i][t]$ 按照贡献系数加入到 $f$ 中，对于非叶子节点，我们只需要枚举左子树内有多少个 $B$ 来更新就好了。就是要注意如果你枚举这个点哪种方案多的时候要保证 $B$ 的个数合法。

这样的话有一个问题：我们开不下数组！所以我们直接在dfs的时候把状态记下来，也就不用开第三维了，也就是我们现在dfs到了一个非叶子节点，我们先把状态设为0，然后dfs子树，更新对应的值，再把状态设为1再dfs一遍子树，给个伪代码：

function dfs(x,l,r)
    if l==r
        calculate f[x][0] and f[x][1]
        return
    now[x]=0
    dfs(lson[x])
    dfs(rson[x])
    calculate f[x][0]->f[x][(r-l+1)/2]
    now[x]=1
    dfs(lson[x])
    dfs(rson[x])
    calculate f[x][(r-l+1)/2+1]->f[x][r-l+1]
    return

这样的话复杂度为 $T(n)=4T(\frac{n}{2})+\Theta(n^2)$ ，根据主定理知 $T(n)=\Theta(n^2\log n)$ ，用这道题里的 $n$ 也就是 $\Theta(n2^{2n})$ 。

感觉讲的不是很清楚（我语文不好），大家有问题的话看下代码或者留个言，代码还是很好写的就50多行。

代码：

#include<bits/stdc++.h>
using namespace std;
int c[2100],t[2100],s[2100][2100],f[2100][2100];
int lca(int x,int y)
{
    while(x!=y)x>>=1,y>>=1;
    return x;
}
void dfs(int l,int r,int x,int now,int dep)//0->0多  1->1多
{
    if(l==r)
    {
        if(t[x]==0)f[x][0]=0,f[x][1]=c[x];//f[x][k] k个1
        else f[x][1]=0,f[x][0]=c[x];
        for(int i=0,j=x>>1;i<dep;i++,j>>=1)
            if(now&(1<<i))f[x][0]+=s[x][j];
            else f[x][1]+=s[x][j];
        return;
    }
    int mid=(l+r)>>1,sum=r-l+1;
    dfs(l,mid,x*2,now*2,dep+1);
    dfs(mid+1,r,x*2+1,now*2,dep+1);// 0 多
    for(int i=0;i<=sum/2;i++)
    {
        f[x][i]=1e9;
        for(int j=0;j<=i;j++)
            f[x][i]=min(f[x][i],f[x*2][j]+f[x*2+1][i-j]);
    }
    dfs(l,mid,x*2,now*2+1,dep+1);
    dfs(mid+1,r,x*2+1,now*2+1,dep+1);// 1 多
    for(int i=sum/2+1;i<=sum;i++)
    {
        f[x][i]=1e9;
        for(int j=0;j<=sum/2;j++)
            if(i-j<=sum/2)f[x][i]=min(f[x][i],f[x*2][j]+f[x*2+1][i-j]);
    }
}
int main()
{
    int n,m,x;
    scanf("%d",&n);
    m=1<<n;
    for(int i=m;i<2*m;i++)scanf("%d",&t[i]);
    for(int i=m;i<2*m;i++)scanf("%d",&c[i]);
    for(int i=m;i<2*m;i++)
        for(int j=i+1;j<2*m;j++)
        {
            scanf("%d",&x);
            int g=lca(i,j);
            s[i][g]+=x,s[j][g]+=x;
        }
    dfs(1,m,1,0,0);
    int ans=1e9;
    for(int i=0;i<=m;i++)ans=min(ans,f[1][i]);
    printf("%d",ans);
    return 0;
}