简述

最近准备开始复习背包，看《背包九讲》之前正好随机到了这道题，所以来做一个简单的总结。

原理

首先回忆 01 背包的 DP 递推式：

\[ dp[j] = \max\{ dp[j], dp[j – weight_i] + value_i \} \]

我们可以尝试加一维，记录为第\(x\)优解：\(dp[x][j]\)。如何从之前的更优解合并为次优解是这道题的难点。首先我们发现，对于每一个\(j\)，\(\{ dp[1][j], dp[2][j], dp[3][j], \dots \}\)是单调下降的。那么，我们如果要合并出一个新的单调下降序列，我们就可以使用归并排序的合并方式：只不过不是在两个序列上，而是在两种决策中选择，我们可以把选择第\(i\)个的和不选择的答案虚拟成两个长度为\(k\)的序列，然后用归并的方式合并。

代码

// P1858.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 5050;

int dp[55][MAX_N], k, m, n, wi[MAX_N], vi[MAX_N], tmp[MAX_N];

int main()
{
    scanf("%d%d%d", &k, &m, &n);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &wi[i], &vi[i]);
    memset(dp, 128, sizeof(dp));
    dp[1][0] = 0;
    for (int i = 1; i <= n; i++)
        for (int j = m; j >= wi[i]; j--)
        {
            int ptr1 = 1, ptr2 = 1, ptr = 0;
            while (ptr <= k)
                if (dp[ptr1][j] > dp[ptr2][j - wi[i]] + vi[i])
                    tmp[++ptr] = dp[ptr1++][j];
                else
                    tmp[++ptr] = dp[ptr2++][j - wi[i]] + vi[i];
            for (int pt = 1; pt <= k; pt++)
                dp[pt][j] = tmp[pt];
        }
    int ans = 0;
    for (int i = 1; i <= k; i++)
        ans += dp[i][m];
    printf("%d", ans);
    return 0;
}

主要思路

首先需要知道一个性质：如果第一行和第一列确定，那么这个方案就已经完全确定了。这个可以用归纳法证明：

证明  如果格子\((i – 1, j)\)、\((i, j – 1)\)和\((i – 1, j – 1)\)的颜色确定，那么显然\((i, j)\)的颜色就能被唯一确定。如果第一行和第一列可以被确定，那么根据上述描述，便可生成一个唯一的方案。

所以欲记录方案的个数，那么就要记录合法的第一行和第一列的方案数。这样我们把问题转换到了长条上。

设置\(dp[i][0/1][0/1]\)为到第\(i\)位是否连续、最后一位填的数字。那么转移非常自然，可以自行推导（确实啊）。

最后答案就是把所有情况加起来，再减去非法的两种情况（也就是左上角的三格同色的情况）。

Continue reading →