BZOJ4007 [JLOI2015]战争调度 DP+DFS

发布于 2017-10-01  6.08k 次阅读


[toggle hide="yes" title="题目" color=""]
Description
脸哥最近来到了一个神奇的王国,王国里的公民每个公民有两个下属或者没有下属,这种关系刚好组成一个 n 层的完全二叉树。公民i的下属是2*i和2*i+1。最下层的公民即叶子节点的公民是平民,平民没有下属,最上层的是国王,中间是各级贵族。现在这个王国爆发了战争,国王需要决定每一个平民是去种地以供应粮食还是参加战争,每一个贵族(包括国王自己)是去管理后勤还是领兵打仗。一个平民会对他的所有直系上司有贡献度,若一个平民i参加战争,他的某个直系上司j领兵打仗,那么这个平民对上司的作战贡献度为wij。若一个平民i种地,他的某个直系上司j管理后勤,那么这个平民对上司的后勤贡献度为fij,若i和j所参加的事务不同,则没有贡献度。为了战争需要保障后勤,国王还要求不多于m个平民参加战争。国王想要使整个王国所有贵族得到的贡献度最大,并把这件事交给了脸哥。但不幸的是,脸哥还有很多deadline没有完成,他只能把这件事又转交给你。你能帮他安排吗?

Input
第一行两个数 n,m。
接下来 2^(n-1) 行,每行n-1个数,第i行表示编号为2^(n-1)-1+i的平民对其n-1直系上司的作战贡献度,其中第一个数表示对第一级直系上司,即编号为(2^(n-1)-1+i)/2的贵族的作战贡献度wij,依次往上。
接下来2^(n-1)行,每行n-1个数,第i行表示编号为2^(n-1)-1+i的平民对其n-1个直系上司的后勤贡献度,其中第一个数表示对第一级直系上司,即编号为(2^(n-1)-1+i)/2的贵族的后勤贡献度fij,依次往上。

Output
一行一个数表示满足条件的最大贡献值

Sample Input
3 4
503 1082
1271 369
303 1135
749 1289
100 54
837 826
947 699
216 389

Sample Output
6701

HINT
对于 100% 的数据,2<=n<=10,m<=2^n-1,0<=wij,fij<=2000

[/toggle]

考试的时候先想到的是确定了最下面一排的选择情况后,上面的点只要扫一遍就一定能确定了,之后去打了状压暴力。。。

实际上,如果反着想,如果上面的点确定后,下面的点选择情况也一定能确定,因为最下面每个点产生的贡献只与它的所有祖先节点有关。接着,如果我们已经确定了当前枚举到的一个点,并且该点上方所有祖先节点的状态均已确定,那么该点的左右两棵子树的状态就是独立的,也就是说我们只需将该状态下左右两棵子树的最大贡献加起来即可。

设f[i][j]:在i点的所有祖先节点的状态确定的情况下,在i点的子树中选择j个黑点的最优解。

那么,我们就有了一个具体思路:先不考虑题目给出的选黑点数的限制,那么深度为i(定义第一层深度为1)的点的子树内,最多选择2^(n-i-1)个黑点,那么我们就直接枚举当前点的两个状态,同时对两个子节点各进行两次DFS,即可确定当前路径选择情况下,子树对应选择黑点数对答案的贡献。接着,枚举当前点选择的黑点数,以及左子树的黑点数,那么右子树的黑点数也确定了,就可以更新当前点的最优解了。最后在输出时,只要在根节点中考虑m的限制就好了。

实现的细节上,每次递归到x时,清空f[x],因为此时x之前的路径状态已经改变,这样就可以考虑到题设的限制了。关于时间复杂度,第i层的每个节点会被访问2^(i-1)次,第i层有2^(i-1)个节点,也就是说,递归的次数最多有大约(2^(2n)-n)/3次,再算上每次递归枚举的子节点数,时间复杂度是可过的(算错了不要怪我= =)。

 


Narcissus | HZOIer | zhuohaoyu1228@gmail.com | QQ 943382974