[JLOI 2015]战争调度

Description

题库链接

给你一棵 \(n\) 层的满二叉树，每个节点可选择为黑或者白。所有的叶子节点都会产生一定的贡献值，具体地，它与其祖先选色相同时会有特定的值（输入给定）。问如何染色使得所有贡献和最大。并且规定染成黑色的叶子节点不能超过 \(m\) 个。

\(1\leq n\leq 10\)

Solution

容易发现一个节点的贡献只与其 \(n-1\) 个祖先有关。我们可以枚举祖先节点的状态进而得到每个叶子的贡献。

然后对于不能超过 \(m\) 个的限制，我们可以记 \(f_{i,j}\) 表示节点 \(i\) 的子树中选出了 \(j\) 个黑点，树形 \(\text{DP}\) 解决。

根据主定理，复杂度是 \(O(n\cdot 2^{2n})\)。

Code

#include 
using namespace std;
const int N = 1024+5;

int n, m;
int f[N][N], v[N], w[N][10], a[N][10];

void dfs(int u, int k) {
    for (int i = 0; i <= (1<