$网络收费$

点击标题链接查看题目.

$<mstyle mathcolor="blue"> 最初想法 </mstyle>$

类似线段树建出一颗树, 暴力枚举每个节点改不改 .

$<mstyle mathcolor="red"> 正解部分 </mstyle>$

观察题目的表格, 可以发现:

满足 $N a < N b$ 的子树上, 只有 $A$ 收费方式需要付费 .
满足 $N a \geq N b$ 的子树上, 只有 $B$ 收费方式需要付费 .

但是此题为两两配对产生贡献,
直接计算时间复杂度为 $O (N^{2})$ , 考虑将两个点拆开一个一个去计算 .
每个 非叶节点 都表示了若干点对的 $L C A$ , 结合上方观察得出的结论, 每个节点对答案造成的贡献都可看作在 非叶节点 造成的 .
则设 $c o s t [i, j]$ 表示 $i$ 这个 叶节点, 在深度为 $j$ 的 祖先(非叶节点) 中与若干点配对产生的 总流量(费用), 可以 $O (N^{2})$ 预处理.

设 $F [i, j]$ 表示以 $i$ 号节点为根的子树, 管辖的叶子节点中含有 $j$ 个 $B$ 收费方式叶子节点的最小花费,
则
$F [k, i + j] = \min (F [l e f t_s o n_{i}, i] + F [r i g h t_s o n_{i}, j]) <mtext> </mtext> c n t_{b} \in [0, s i z e_{i}]$

若 $N a < N b$ 需要满足条件 $s i z e_{i} - i - j < i + j$
若 $N a \geq N b$ 需要满足条件 $s i z e_{i} - i - j \geq i + j$

这样往下递归, 每次假定当前节点 $N a < N b$ 还是 $N a \geq N b$ .

到了叶子节点就可以直接计算这个叶子节点产生的贡献了, 具体地说:

设当前递归到了 叶子节点 $a$ ,

若当前为 $A$ 付费方式, 对答案的贡献为 $F [a, 0] = \sum_{i = 0}^{m a x_d e p}! t m p [i] * c o s t [a, i]$ .
若当前为 $B$ 付费方式, 对答案的贡献为 $F [a, 1] = \sum_{i = 0}^{m a x_d e p} t m p [i] * c o s t [a, i]$ .

在上方的答案统计中, 当且仅当目前收费方式与初始收费方式不同时, 需要加上修改产生的花费 .

$<mstyle mathcolor="red"> 实现部分 </mstyle>$

对收费方式的处理: 使用 $C [0 / 1] [i]$ 表示第 $i$ 个用户使用 $A / B$ 收费方式时的修改费用, 递归到叶子节点时赋初值可以方便地处理修改产生的费用 .

$t m p [d e p] = 0$ 表示当前 $D F S 链$ 中深度为 $d e p$ 的 当前节点 以下 $N a < N b$ , 只有 $A$ 付费.
$t m p [d e p] = 1$ 则表示 $N a \geq N b$ , 只有 $B$ 付费 .

求解 $L C A$ 深度时, 可以不断 “试” 两个待测节点 $x, y$ , 具体地说:
不断的对 $x, y$ 执行 $> > i$ 操作, 相当于向上走 $i$ 步, 当它们走到的节点不同时, 那两个不同的节点的父亲即为 $L c a$ , 深度为 $m a x_d e p - i - 1$ .

#include<bits/stdc++.h>
#define reg register
typedef long long ll;

const int maxn = 3500;

int n;
int N;
int tmp[13];
int Fs[maxn];
ll C[2][maxn];
ll F[maxn][maxn];
ll cost[maxn][13];

int Lca(int x, int y){
        for(reg int i = n; i >= 0; i --)
        	if((x>>i) != (y>>i)) return n-i-1;
}

void DFS(int k, int dep, int l, int r){
        if(dep == n){
                F[k][0] = C[0][l], F[k][1] = C[1][l];
                for(reg int i = 0; i < dep; i ++) F[k][tmp[i]] += cost[l][i];
                return ;
        }

        int mid = l+r >> 1;

	memset(F[k], 0x3f, sizeof F[k]);

        tmp[dep] = 0;
        DFS(k<<1, dep+1, l, mid), DFS(k<<1|1, dep+1, mid+1, r);
        for(reg int i = 0; i <= mid-l+1; i ++)
                for(reg int j = 0; j <= mid-l+1; j ++){
                	if(r-l+1-i-j >= i+j) continue ;
			F[k][i+j] = std::min(F[k][i+j], F[k<<1][i] + F[k<<1|1][j]);
		}

        tmp[dep] = 1;
        DFS(k<<1, dep+1, l, mid), DFS(k<<1|1, dep+1, mid+1, r);
        for(reg int i = 0; i <= mid-l+1; i ++)
                for(reg int j = 0; j <= mid-l+1; j ++){
                	if(r-l+1-i-j < i+j) continue ;
			F[k][i+j] = std::min(F[k][i+j], F[k<<1][i] + F[k<<1|1][j]);
		}
}

int main(){
        scanf("%d", &n); N = 1 << n;
        for(reg int i = 1; i <= N; i ++) scanf("%d", &Fs[i]);
        for(reg int i = 1; i <= N; i ++) scanf("%lld", &C[!Fs[i]][i]), C[Fs[i]][i] = 0;
        for(reg int i = 1; i <= N; i ++)
                for(reg int j = i+1; j <= N; j ++){
                        int x; scanf("%d", &x);
                        int lca_dep = Lca(i-1, j-1);
                        cost[i][lca_dep] += x, cost[j][lca_dep] += x;
                }
        DFS(1, 0, 1, N);
        ll Ans = 1e18;
        for(reg int i = 0; i <= N; i ++) Ans = std::min(Ans, F[1][i]);
        printf("%lld\n", Ans);
        return 0;
}

P4297 [NOI2006]网络收费 [树形dp]

网 络 收 费 网络收费 网络收费

<mstyle mathcolor="blue"> 最 初 想 法 </mstyle> \color{blue}{最初想法} 最初想法

<mstyle mathcolor="red"> 正 解 部 分 </mstyle> \color{red}{正解部分} 正解部分

<mstyle mathcolor="red"> 实 现 部 分 </mstyle> \color{red}{实现部分} 实现部分

$网络收费$

$<mstyle mathcolor="blue"> 最初想法 </mstyle>$

$<mstyle mathcolor="red"> 正解部分 </mstyle>$

$<mstyle mathcolor="red"> 实现部分 </mstyle>$