0%

「NOI2006」网络收费

发表于 更新于 阅读次数： Valine：

题目链接

神仙题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一遍子树，给个伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
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多行。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#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;
}