1 条题解

  • 0
    @ 2026-11-15 22:43:21

    D 冒险者的奖励之路 - 题解

    题目分析

    这是一道关于有向无环图(DAG)上的状态压缩动态规划问题。关键观察如下:

    核心观察

    1. 图的特性:由于地点按高度从低到高排列,且传送门只能从低处到高处,所以这是一个有向无环图(DAG)。

    2. 公司分类:

      • 第一类公司:只开一家连锁店的公司(color_count[i] == 1)
      • 第二类公司:开多家连锁店的公司(color_count[i] > 1)
    3. 关键优化:

      • 对于第一类公司,由于只有一家店,任何路径都无法访问多次,因此可以无视"每家公司的红包只能领一份"的限制
      • 对于第二类公司,由于最多有 n2≤18\frac{n}{2} \leq 18 家(因为每家至少开2家店),可以使用状态压缩

    算法思路

    状态定义

    设 dp[i][S] 表示从节点1出发到达节点i,访问过的第二类公司集合为S时,能获得的最大红包总价值。

    状态转移

    1. 初始化:从节点1开始,根据其所属公司类型设置初始状态
    2. 转移过程:枚举所有可达的节点对 (i, j),对于每个状态S:
      • 如果节点j属于第一类公司:直接转移,状态不变
      • 如果节点j属于第二类公司且未访问过:更新状态并转移

    算法步骤

    1. 预处理:

      • 统计每种颜色的出现次数
      • 为重复颜色分配新编号
      • 使用Floyd算法计算可达性
    2. 动态规划:

      • 初始化第一个节点的状态
      • 枚举所有节点对和状态进行转移
    3. 输出结果:

      • 对每个节点,枚举所有可能的状态,取最大值

    复杂度分析

    • 时间复杂度:O(n2⋅2n/2)O(n^2 \cdot 2^{n/2})
      • Floyd算法:O(n3)O(n^3)
      • 状态压缩DP:O(n2⋅2n/2)O(n^2 \cdot 2^{n/2}),其中 n/2≤18n/2 \leq 18
    • 空间复杂度:O(n⋅2n/2)O(n \cdot 2^{n/2})

    代码实现要点

    1. 公司分类处理

    // 统计颜色出现次数
    for (int i = 1; i <= n; i++) {
        cin >> color[i];
        color_count[color[i]]++;
    }
    
    // 为重复颜色分配编号
    for (int i = 1; i <= n; i++) {
        cin >> weight[i];
        if (color_count[i] > 1) {
            color_id[i] = unique_colors++;
        }
    }
    

    2. 可达性计算

    // Floyd算法计算可达性
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i != j) {
                    graph[i][j] |= (graph[i][k] & graph[k][j]);
                }
            }
        }
    }
    

    3. 状态压缩DP

    // 初始化
    if (color_count[color[1]] == 1) {
        dp[1][0] = weight[color[1]];
    } else {
        dp[1][1LL << color_id[color[1]]] = weight[color[1]];
    }
    
    // 状态转移
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (!graph[i][j]) continue;
            
            for (int state = 0; state < (1LL << unique_colors); state++) {
                if (color_count[color[j]] == 1) {
                    // 第一类公司,直接转移
                    dp[j][state] = max(dp[j][state], dp[i][state] + weight[color[j]]);
                } else if (!(state & (1LL << color_id[color[j]]))) {
                    // 第二类公司且未访问过
                    int new_state = state | (1LL << color_id[color[j]]);
                    dp[j][new_state] = max(dp[j][new_state], dp[i][state] + weight[color[j]]);
                }
            }
        }
    }
    
    • 1

    信息

    ID
    220
    时间
    1000ms
    内存
    512MiB
    难度
    5
    标签
    递交数
    1
    已通过
    1
    上传者