a173: NOI2006 Day1.1.网络收费
Tags :
Accepted rate : 10人/10人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2014-11-01 03:14

Content

网络已经成为当今世界不可或缺的一部分。每天都有数以亿计的人使用网络
进行学习、科研、娱乐等活动。然而,不可忽视的一点就是网络本身有着庞大的
运行费用。所以,向使用网络的人进行适当的收费是必须的,也是合理的。


MY 市NS 中学就有着这样一个教育网络。网络中的用户一共有2N 个,编号
依次为1, 2, 3, …, 2N。这些用户之间是用路由点和网线组成的。用户、路由点与
网线共同构成一个满二叉树结构。树中的每一个叶子结点都是一个用户,每一个
非叶子结点(灰色)都是一个路由点,而每一条边都是一条网线(见下图,用户
结点中的数字为其编号)。


MY 网络公司的网络收费方式比较奇特,称为“ 配对收费 ”。即对于每两个
用户i, j (1≤i < j ≤2N ) 进行收费。由于用户可以自行选择两种付费方式A、B
中的一种,所以网络公司向学校收取的费用与每一位用户的付费方式有关。该费
用等于每两位不同用户配对产生费用之和。


为了描述方便,首先定义这棵网络树上的一些概念:
祖先:根结点没有祖先,非根结点的祖先包括它的父亲以及它的父亲的祖先;
管辖叶结点:叶结点本身不管辖任何叶结点,非叶结点管辖它的左儿子所管
辖的叶结点与它的右儿子所管辖的叶结点;
距离:在树上连接两个点之间的用边最少的路径所含的边数。


对于任两个用户i, j (1≤i<j≤2N ),首先在树上找到与它们距离最近的公共
祖先:路由点P,然后观察P 所管辖的叶结点(即用户)中选择付费方式A 与B
的人数,分别记为nA 与nB,接着按照网络管理条例第X 章第Y 条第Z 款进行
收费(如下表),其中Fi, j 为i 和j 之间的流量,且为已知量。

 

i 付费方式

j 付费方式nA nB 大小关系付费系数k实际付费
AAnAnB2k*Fi,j
AB1
BA1
BB0
AA

nAnB

0
AB1
BA1
BB2

由于最终所付费用与付费方式有关,所以NS 中学的用户希望能够自行改变
自己的付费方式以减少总付费。然而,由于网络公司已经将每个用户注册时所选
择的付费方式记录在案,所以对于用户i,如果他/她想改变付费方式(由A 改为
B 或由B 改为A),就必须支付Ci 元给网络公司以修改档案(修改付费方式记录)。


现在的问题是,给定每个用户注册时所选择的付费方式以及Ci,试求这些用
户应该如何选择自己的付费方式以使得NS 中学支付给网络公司的总费用最少
(更改付费方式费用+配对收费的费用)。

Input

输入文件中第一行有一个正整数N。


第二行有2^N 个整数,依次表示1 号,2 号,…,2^N 号用户注册时的付费方式,
每一个数字若为0,则表示对应用户的初始付费方式为A,否则该数字为1,表
示付费方式为B。


第三行有2^N 个整数,表示每一个用户修改付费方式需要支付的费用,依次为
C1, C2, …,CM 。( M=2^N )


以下 2^N-1 行描述给定的两两用户之间的流量表F,总第(i + 3)行第j 列的整
数为Fi, j+i 。(1≤i<2^N,1≤j≤2^N – i)
所有变量的含义可以参见题目描述。

Output
你的程序只需要向输出文件输出一个整数,表示NS 中学支付给网络公司的
最小总费用。(单位:元)
Sample Input
2
1 0 1 0
2 2 10 9
10 1 2
2 1
3
Sample Output
8
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (10%): 3.0s , <1K
公開 測資點#1 (10%): 3.0s , <1K
公開 測資點#2 (10%): 3.0s , <1K
公開 測資點#3 (10%): 3.0s , <1K
公開 測資點#4 (10%): 3.0s , <1M
公開 測資點#5 (10%): 3.0s , <1M
公開 測資點#6 (10%): 3.0s , <1M
公開 測資點#7 (10%): 3.0s , <1M
公開 測資點#8 (10%): 3.0s , <10M
公開 測資點#9 (10%): 3.0s , <10M
Hint :

将 1 号用户的付费方式由B 改为A,NS 中学支付给网络公司的费用达到最
小。

【数据规模和约定】
40%的数据中N≤4;
80%的数据中N≤7;
100%的数据中N≤10,0≤Fi, j≤500,0≤Ci≤500 000。

Tags:
出處:
NOI2006Day1第一题 [管理者:
liouzhou_101 (王启圣)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」