P6808 Candies 题解

鲜花

校内模拟赛T3，赛时想到了正解的 60\%，所以就得了 60 分……

赛后 T 了若干发之后终于过了。

本文提供一种非回退背包的解法。

在下文中，记 k = \sum_{i = 1}^n a_i。

Solution 1

假设我们修改 a_i，设用其他数拼出的方案数为 cnt_i ，那么当 a_i' 足够大时，有 {cnt_i'}_{max} = 2cnt_i + 1。所以问题就转化到了求 \max_{i = 1}^{n} cnt_i 与 i。

考虑枚举 i，并对于每个 i 进行 DP 计算 cnt_i。求出最大值与最大值位置（即 p）后，需要求 q。

设 f_i 表示是否能凑出 i。很容易发现，当 \sum_{i = 1}^k [f_i = 1, f_{i + q} = 1] = 0 时，q 合法。暴力枚举即可。

时间复杂度 O(n ^ 2k + k ^ 2)，完全不能接受。

Solution 2

我们发现，在第一种解法中，对于同一个物品，进行了太多次的背包 DP。我们尝试只进行一次DP，并标记为了凑出当前这个数，有哪些位置必须被选取。若不需要选取第 i 个数，代表当我们修改 a_i 时仍然能凑出这个数。

具体地，设 dp_{i, j} 表示为了凑出 i，是否需要 a_j。转移方程如下。

f_i = \mathop{bitor}\limits_{1\le k\le n} f_{i - a_k}\\ \ \\ dp_{i, j}= \mathop{bitand}\limits_{1\le k\le n,\ f_{i - a_k} = 1} \begin{cases} dp_{i - a_k, j}\ (j \ne k)\\ 1\ (j = k) \end{cases}

DP 完之后统计 cnt_i，剩余步骤与解法一相同。

时间复杂度仍然是 O(n ^ 2k + k ^ 2)，但常数好得多，在洛谷上取得了 60 分的好成绩！（这也是我赛时的做法，个人认为特别符合直觉。）

Solution 3

考虑优化一下求 q 的过程。前文已推得，当 \sum_{i = 1}^k [f_i, f_{i + q}] \ne 0，q 不合法。设全集（可重集）为 U，此时有可重集 S, T 满足 S, T \subset U, (\sum_{i \in S} b_i) - (\sum_{i \in T} b_i) = q。再正反做一次背包即可。总时间复杂度 O(n^2k)，还是卡。

Solution 4

由于所有状态都是 0 或 1，所以可以用 bitset 优化。最终复杂度 O(\frac{n ^ 2k}{w})，趋近于 O(nk)，可以通过。

Code

在代码中，dp[i][0] 代表文中的 f_i，其余的 dp[i][j] 代表文中的 dp_{i, j}。

int n, a[105], sum, cnt[105], mx, p;
bitset<105> dp[700005];
bitset<1400005> tmp;

int main() {
    read(n);
    for(int i = 1; i <= n; ++i)
        read(a[i]), sum += a[i];
    // 初始化 dp 数组
    sort(a + 1, a + 1 + n);
    dp[0] = 1, dp[1][0] = 0;
    for(int i = 1; i <= n; ++i)
        dp[1][i] = 1;
    for(int i = 2; i <= sum; ++i)
        dp[i] = dp[i - 1];
    // 计算 dp 数组
    for(int i = 1; i <= n; ++i)
        for(int j = sum; j >= a[i]; --j)
            if(dp[j - a[i]][0]) {
                dp[j] &= dp[j - a[i]];
                if(!dp[j][0]) dp[j][i] = 1;
                dp[j][0] = 1;
            }
    // 统计 cnt 并计算 p
    for(int i = 1; i <= sum; ++i)
        if(dp[i][0])
            for(int j = 1; j <= n; ++j)
                if(!dp[i][j])
                    ++cnt[j];
    mx = p = 0;
    for(int i = 1; i <= n; ++i)
        if(cnt[i] > mx) mx = cnt[i], p = i;
    // 计算 q
    tmp[7000 * n] = 1;
    for(int i = 1; i <= n; ++i)
        if(i != p)
            tmp = tmp | (tmp << a[i]) | (tmp >> a[i]);
    for(int i = 1; i <= sum - a[p] + 1; ++i)
        if(!tmp[7000 * n + i])
            return printf("%d %d\n", a[p], i), 0;
}

这代码截止发题解当天竟然还跑出了洛谷最优解。（不过做这道题的人少。）