1 条题解
-
0
D 冒险者的奖励之路 - 题解
题目分析
这是一道关于有向无环图(DAG)上的状态压缩动态规划问题。关键观察如下:
核心观察
-
图的特性:由于地点按高度从低到高排列,且传送门只能从低处到高处,所以这是一个有向无环图(DAG)。
-
公司分类:
- 第一类公司:只开一家连锁店的公司(
color_count[i] == 1) - 第二类公司:开多家连锁店的公司(
color_count[i] > 1)
- 第一类公司:只开一家连锁店的公司(
-
关键优化:
- 对于第一类公司,由于只有一家店,任何路径都无法访问多次,因此可以无视"每家公司的红包只能领一份"的限制
- 对于第二类公司,由于最多有 家(因为每家至少开2家店),可以使用状态压缩
算法思路
状态定义
设
dp[i][S]表示从节点1出发到达节点i,访问过的第二类公司集合为S时,能获得的最大红包总价值。状态转移
- 初始化:从节点1开始,根据其所属公司类型设置初始状态
- 转移过程:枚举所有可达的节点对
(i, j),对于每个状态S:- 如果节点j属于第一类公司:直接转移,状态不变
- 如果节点j属于第二类公司且未访问过:更新状态并转移
算法步骤
-
预处理:
- 统计每种颜色的出现次数
- 为重复颜色分配新编号
- 使用Floyd算法计算可达性
-
动态规划:
- 初始化第一个节点的状态
- 枚举所有节点对和状态进行转移
-
输出结果:
- 对每个节点,枚举所有可能的状态,取最大值
复杂度分析
- 时间复杂度:
- Floyd算法:
- 状态压缩DP:,其中
- 空间复杂度:
代码实现要点
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
- 上传者