思路

这道题是一道动态规划的题目。我们首先考虑预处理出一个数组，来存放两两单词是否安全。之后我们再利用这个信息来进行DP。而有一个值得注意的要点是：我们在动态规划时要消除后效性，否则就会出现错误。在本题中，我们需要对字符串进行排序，因为排序后不安全的单词只存在于在第\(i\)个单词的前面，这样我们用一维\(dp\)即可。考虑方程：\(dp[j] += dp[i], j \in [i, n], possible[i][j] == true\)即可。

Continue reading →

思路

这道题观察数据范围和题干，可以得知这是一道状压dp的题目。我们先来设计状态：在本题中，可以类比互不侵犯的那一题（互不侵犯题解），设计成当前状态和上一状态相关的元素。可以想出，dp[当前牛的存在情况][当前加入的牛的编号] += dp[上一次加入后的状态][上一次加入的牛的编号];

基本上完成了思考，现在我们先来搞定预处理。我们把只有cowId在队列里的方案数初始化为1。

for (int cowId = 0; cowId < n; cowId++)
        dp[1 << cowId][cowId] = 1;

之后我们就可以进行dp了。详细见代码：

for (int lastState = 0; lastState < (1 << n); lastState++)
    for (int lastCow = 0; lastCow < n; lastCow++)
        if (lastState & (1 << lastCow))
            for (int nowCow = 0; nowCow < n; nowCow++)
                if (!(lastState & (1 << nowCow)) && abs(seq[nowCow] - seq[lastCow]) > k)
                    nowState = lastState | (1 << nowCow),
                    dp[nowState][nowCow] += dp[lastState][lastCow];

最后方案数叠加，在满员的状态下枚举最后一头牛的id。

ll ans = 0;
for (int i = 0; i < n; i++)
    ans += dp[(1 << n) - 1][i];
cout << ans;

代码

// P2915.cpp
#include <iostream>
#include <cmath>
using namespace std;

#define ll unsigned long long
const int maxn = 16;
ll dp[1 << maxn][maxn];
int n, k, nowState;
int seq[maxn];

int main()
{
    cin >> n >> k;
    for (int i = 0; i < n; i++)
        cin >> seq[i];
    for (int cowId = 0; cowId < n; cowId++)
        dp[1 << cowId][cowId] = 1;
    for (int lastState = 0; lastState < (1 << n); lastState++)
        for (int lastCow = 0; lastCow < n; lastCow++)
            if (lastState & (1 << lastCow))
                for (int nowCow = 0; nowCow < n; nowCow++)
                    if (!(lastState & (1 << nowCow)) && abs(seq[nowCow] - seq[lastCow]) > k)
                        nowState = lastState | (1 << nowCow),
                        dp[nowState][nowCow] += dp[lastState][lastCow];
    ll ans = 0;
    for (int i = 0; i < n; i++)
        ans += dp[(1 << n) - 1][i];
    cout << ans;
    return 0;
}

思路

这是一道状压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;
}