思路

这是一道状压dp的题目，在此之前我没有学过状压dp，今天上午在dalao lornd的讲解下我理解了状压dp。然而我的能力有限，不能广义上来总结状压dp这个骚操作。状压dp的精髓就在于把多个状态合并为二进制数，然后再进行子集生成。我们这里设计一个状态，这个状态包含了当行棋子的摆放方式。比如，01110代表中间三个位置放置了棋子，为了简便，我们把这个状态可以直接压缩成14这个十进制的数字。这就是状态压缩。

我强烈建议读者学习完位运算的基本知识之后再来阅读状态压缩的文章，这样理解起来才能事半功倍。

之后我们搞懂了如何压缩状态之后，我们来进行dp。首先我们先要来预处理，预处理的几个目标是：计算单行的状态，计算两行之间的状态，计算每个状态的棋子数量。

计算单行和棋子的数量的状态比较简单，在[0,2^32)之间枚举出状态，判定是否有两个1相邻。如果有的话，那么在状态表中设置成false，表示这个状态不能被利用，即不能被纳入计算。具体代码如下：

for (int i = 0; i < MAX; i++)
    {
        // check if there are pairs of 1;
        if (i & (i >> 1))
            continue;
        // checked and set it true;
        sigLine[i] = true;
        // get the number of 1 within the state and record them;
        for (int j = 1; j <= i; j <<= 1)
            if (j & i)
                king[i]++;
    }

其中我们设置MAX = 1 << n，即状态的上限。至于为什么小于MAX而不是小于等于MAX，读者可以思考这两者是否有区别。

之后我们要计算两行之间的状态，我们开一个数组叫\(doubleLine[1<<maxn][1<<maxn]\)，其中如果\(doubleLine[x][y]==true\)，说明第一行的状态为x且第二行状态为y是可以存在的，可以被纳入计算的。这样的话，不难想出用暴力的方法来进行预处理：

// the first line;
    for (int i = 0; i < MAX; i++)
        if (sigLine[i])
            // the second line;
            for (int j = 0; j < MAX; j++)
                // check if these two are valid.
                if (sigLine[j] && !(i & j) && !(i & (j << 1)) && !(i & (j >> 1)))
                    // set!
                    doubleLine[i][j] = true;

我们预处理工作差不多了，接下来我们来进行动态规划的递推编写了。首先我们先来设计方程，不难想出方程：

\(dp[前n行数][累计w个棋子][本行的状态] = 当前状态数\)

\(dp[i+1][w+king[next]][nextLine] = dp[i][w][currentLine]\)

最后，我们把在n行上、棋子数量为k的所有状态枚举一边，便可以累计得出答案。特别注意的是，这道题目需要long long的数据范围，小心溢出。

代码

// P1896.cpp
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

const int maxn = 11;
#define ll long long
int MAX;
int n, k;
bool sigLine[1 << maxn];
bool doubleLine[1 << maxn][1 << maxn];
int king[1 << maxn];
ll dp[maxn][100][1 << maxn];

int main()
{
    cin >> n >> k;
    MAX = 1 << n;
    for (int i = 0; i < MAX; i++)
    {
        // check if there are pairs of 1;
        if (i & (i >> 1))
            continue;
        // checked and set it true;
        sigLine[i] = true;
        // get the number of 1 within the state and record them;
        for (int j = 1; j <= i; j <<= 1)
            if (j & i)
                king[i]++;
    }
    // the first line;
    for (int i = 0; i < MAX; i++)
        if (sigLine[i])
            // the second line;
            for (int j = 0; j < MAX; j++)
                // check if these two are valid.
                if (sigLine[j] && !(i & j) && !(i & (j << 1)) && !(i & (j >> 1)))
                    // set!
                    doubleLine[i][j] = true;
    for (int i = 0; i <= MAX; i++)
        if (sigLine[i])
            dp[1][king[i]][i] = 1;
    for (int i = 1; i < n; i++)
        for (int poss = 0; poss < MAX; poss++)
            if (sigLine[poss])
                for (int nextLine = 0; nextLine < MAX; nextLine++)
                    if (sigLine[nextLine] && doubleLine[poss][nextLine])
                        for (int w = king[poss]; w + king[nextLine] <= k; w++)
                            dp[i + 1][w + king[nextLine]][nextLine] += dp[i][w][poss];
    ll ans = 0;
    for (int i = 0; i < MAX; i++)
        ans += dp[n][k][i];
    cout << ans;
    return 0;
}

思路

一开始我还以为是拓扑排序，后面写代码的时候仔细思考了这道题，应该是树形dp。

主要的思路就是做一个编号为0的虚拟节点（这个点权重（学分）为0），然后建一棵树。构造dp方程\(F[u][size] = F[son][subsize] + F[u][size – subsize]\)。其中这里需要注意的是，这个本质上是一个树形的01背包，所以在生成dp表的时候需要反着推。（坑了我一个小时，哎我还是太菜了）输出的时候因为有点0的存在所以背包容量会比之前的大一个单位。

还需要注意的是，在我的代码中，我用了一个dfss来计算每个子背包的容量，不知道有没有必要，希望大佬能指出是否有这个必要。

代码

// P2014.cpp
#include <iostream>
#include <queue>
using namespace std;

const int maxn = 2100;
struct edge
{
    int to, next;
} edges[maxn << 1];
int deg[maxn];
int indeg[maxn];
int head[maxn];
int weight[maxn];
int current = 0;

int n, m;

void addpath(int src, int dst)
{
    edges[current].to = dst;
    edges[current].next = head[src];
    head[src] = current++;
}

int F[maxn][maxn];
int sizes[maxn];

void dfss(int u)
{
    sizes[u] = 1;
    for (int i = head[u]; i != -1; i = edges[i].next)
    {
        dfss(edges[i].to);
        sizes[u] += sizes[edges[i].to];
    }
}

void dfs(int u)
{
    for (int i = 1; i <= m; i++)
        F[u][i] = weight[u];
    for (int i = head[u]; i != -1; i = edges[i].next)
    {
        dfs(edges[i].to);
        int jto = edges[i].to;
        for (int len = m + 1; len >= 2; len--)
            for (int lens = 0; lens < len; lens++)
                F[u][len] = max(F[u][len], F[u][len - lens] + F[jto][lens]);
    }
}

int main()
{
    fill(head, head + maxn, -1);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        int k, s;
        cin >> k >> s;
        weight[i] = s;
        addpath(k, i), indeg[i]++, deg[k]++;
    }
    dfss(0);
    dfs(0);
    cout << F[0][m + 1];
    return 0;
}

思路

这是一道非常经典的树形DP，题中直接讲到这是树形结构。建树之后，状态转移方程不难想出：

• 对于每一个点，F[u][0]代表不选这个点的最优解，F[u][1]代表选这个点的最优解。
• 对于运行时的每个点，都有F[u][1] = happiness[u]。
• 对于一个点的孩子遍历，都有F[u][0] += max(F[v][1], F[v][0])，F[u][1] += F[v][0]。

由此，我们可以轻松的写出下列的代码。

代码

// P1352.cpp
#include <iostream>

using namespace std;
// Data Structure;
const int maxn = 6100;
int n;
int R[maxn];
// Graph stuff;
// Notice: the edge space should be doubled;
struct edge
{
    int to, next;
} edges[maxn << 1];
int head[maxn];
int current = 0;
int F[maxn][2];
int deg[maxn];
// DFS func;
void DFS(int curt)
{
    // Initalize the DP Table;
    F[curt][1] = R[curt];
    // Find the subnodes;
    for (int i = head[curt]; i != -1; i = edges[i].next)
    {
        // Call the subtree to be ready;
        DFS(edges[i].to);
        // Deciding;
        F[curt][1] += F[edges[i].to][0];
        F[curt][0] += max(F[edges[i].to][0], F[edges[i].to][1]);
    }
}

void add_path(int src, int dst)
{
    edges[current].to = dst;
    edges[current].next = head[src];
    head[src] = current++;
}

int main()
{
    // Initialize;
    cin >> n;
    fill(head, head + maxn, -1);
    for (int i = 1; i <= n; i++)
        cin >> R[i];
    int a, b;
    for (int i = 1; i <= n - 1; i++)
    {
        cin >> a >> b, add_path(b, a);
        deg[a]++;
    }
    cin >> a >> b;
    // Find the root node by the degrees saved before;
    int root = 0;
    for (int i = 1; i <= n; i++)
        if (deg[i] == 0)
        {
            root = i;
            break;
        }
    // Start to dp;
    DFS(root);
    // Output;
    cout << max(F[root][0], F[root][1]);
    return 0;
}