1 条题解

  • 0
    @ 2026-11-12 21:58:12

    [U] Grouping(dp_u)题解

    题意简述

    NN 只兔子,分成若干组,同组内的每对 (i,j)(i,j) 贡献 ai,ja_{i,j},求总分最大值。N≤16N \le 16。

    思路

    预处理:每组内部的收益

    设 gSg_S = 集合 SS 的兔子全分在同一组时的总收益:

    gS=∑i<j,  i,j∈Sai,j.g_S = \sum_{i<j,\; i,j \in S} a_{i,j}.

    可以在 O(2N)O(2^N) 内递推:取 SS 的最小元素 ii,则 $g_S = g_{S \setminus \{i\}} + \sum_{j \in S\setminus\{i\}} a_{i,j}$。

    集合划分 DP

    设 fSf_S = 把 SS 划分成若干组能获得的最大收益。枚举"包含 SS 最小元素的那一组" T⊆ST \subseteq S:

    $$f_S = \max_{T \subseteq S,\; \min(S) \in T} \left( f_{S \setminus T} + g_T \right),\qquad f_\emptyset = 0.$$

    答案 ffullf_{\text{full}}。

    固定"含最小元素的组"可以避免同一划分被多种顺序重复枚举。

    为什么可以用"全负时取 0"来理解

    若所有 ai,j<0a_{i,j} < 0,最优解是每只兔子单独一组(组内无对,收益 00)。所以答案下界是 00(样例 2 就是 00)。

    复杂度

    枚举所有子集再枚举子集的子集,总 O(3N)O(3^N);N=16N=16 时 316≈4.3×1073^{16} \approx 4.3\times10^7,可过。空间 O(2N)O(2^N)。

    参考代码

    #include <cstdio>
    #include <algorithm>
    using namespace std;
    
    long long a[16][16], g[1 << 16], f[1 << 16];
    
    int main() {
        int n;
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) scanf("%lld", &a[i][j]);
        int full = 1 << n;
        for (int S = 1; S < full; S++) {
            int lo = __builtin_ctz(S), rest = S ^ (1 << lo);
            g[S] = g[rest];
            for (int m = rest; m; m &= m - 1) g[S] += a[lo][__builtin_ctz(m)];
        }
        for (int S = 1; S < full; S++) {
            int hi = S & -S;                 // 最小元素,必须属于被选出的组
            long long best = -(1LL << 60);
            for (int m = S; m; m = (m - 1) & S)
                if (m & hi) best = max(best, f[S ^ m] + g[m]);
            f[S] = best;
        }
        printf("%lld\n", f[full - 1]);
        return 0;
    }
    

    易错点

    1. 必须固定最小元素再枚举组,否则同一划分被重复统计(虽然取 max 不影响结果,但会多算 N!N! 倍时间)。
    2. ai,ja_{i,j} 可为负,ff 的初值要用极小数,不能是 00——否则会把"单独成组"之外的坏方案当成更好。
    3. 结果可达 (162)16 \choose 2 ×109=1.2×1011\times 10^9 = 1.2\times10^{11},必须 long long(样例 3 是 5×1095\times10^9)。
    4. 枚举子集的写法 m = (m-1) & S 别写成 m--。

    数据说明

    共 17 组:4 组官方样例;N=1N=1;N=2N=2 正/负;N=3N=3 正/负;N=5/8/10/12N=5/8/10/12 随机;N=16N=16 全正、全负、混合随机、全 10910^9(最大规模与最大和)。

    • 1

    信息

    ID
    30
    时间
    1000ms
    内存
    256MiB
    难度
    7
    标签
    递交数
    1
    已通过
    1
    上传者