题意理解

我们有 $n$ 个节点（空地），编号 $1 \dots n$，节点 $i$ 的高度就是 $i$。
有 $m$ 条有向边 $a_i \to b_i$，满足 $a_i < b_i \le a_i + k$。
每个节点有一个吸引力 $f_i$。

规则：

• 从某个节点 $p$ 出发，所有摄影师一起走到 $p$，然后分散。
• 每个摄影师只能沿着有向边向上走（即从低编号到高编号）。
• 每个节点最多被一人拍到一次。
• 目标是最大化被拍到的节点的吸引力总和。

我们需要对每个 $p = 1 \dots n$，输出最大吸引力总和。

---

问题转化

实际上，这个问题等价于：
从 $p$ 出发，可以沿着边向上走，可以有多条路径，但不能重复访问节点，求所有可达节点的吸引力总和的最大值。

因为摄影师可以分散走，所以只要是从 $p$ 出发沿着 DAG 能走到的节点，都可以安排一个人去，并且每个节点只算一次吸引力。

所以问题变成：
对于每个 $p$，求从 $p$ 出发能到达的所有节点的吸引力总和的最大值（其实就是所有可达节点的吸引力之和，因为不重复计算）。

---

关键观察

• 图是一个 DAG（节点编号即拓扑序）。
• 边 $(a,b)$ 满足 $b \le a + k$，意味着只能跳到最多往后 $k$ 个节点。
• 因此，从节点 $i$ 出发，能直接到达的节点在 $i+1, i+2, \dots, i+k$ 中。
• 由于 $k \le 8$，这是一个很小的数，可以用状态压缩处理。

---

状态设计

设 $dp[i][S]$ 表示：
当前在节点 $i$，并且 $S$ 是一个 $k$ 位的二进制掩码，表示在接下来的 $k$ 个节点（$i, i+1, \dots, i+k-1$）中，哪些节点已经被访问过（1 表示已访问，0 表示未访问）。

这里 $S$ 的第 0 位对应节点 $i$，第 1 位对应节点 $i+1$，依此类推。

转移：

• 从 $i$ 出发，可以选择走一条边 $i \to j$（$j \in [i+1, i+k]$），前提是 $j$ 在 $S$ 中未被访问（即 $S$ 的第 $j-i$ 位为 0）。
• 转移时，新的掩码 $S'$ 会把 $j$ 标记为已访问，并且整体右移一位（因为 $i$ 变成 $i+1$，掩码对应位置变化）。

---

代码分析

给出的代码正是基于这个思路，但是是倒序 DP：

g[x] |= 1 << (y - x);

这里 g[x] 是一个位掩码，表示从 $x$ 出发能直接到达的相对于 $x$ 的偏移（$y-x \in [1,k]$）。

---

vector<int> dp(1 << k, 0);

dp[S] 表示在当前节点 $i$ 时，掩码 $S$ 表示接下来的 $k$ 个节点中哪些被访问过，能获得的最大吸引力。

---

for (int i = n; i >= 1; i--) {
    vector<int> ndp(1 << k, 0);
    for (int S = 0; S < (1 << k); S++) {
        int nS = S >> 1 | (S & 1 ? (g[i] >> 1) : 0);
        ndp[S] = max(ndp[S], dp[nS] + (S & 1 ? a[i] : 0));
    }
    dp.swap(ndp);
    ans.push_back(dp[1]);
}

解释：

• 倒序 DP：从 $n$ 到 $1$。
• S 是当前掩码，nS 是转移到下一个节点 $i+1$ 时的新掩码。
• S >> 1：因为从 $i$ 到 $i+1$，掩码右移一位（原来第 1 位对应 $i+1$，现在变成第 0 位对应 $i+1$）。
• (S & 1 ? (g[i] >> 1) : 0)：如果 $S$ 的第 0 位（对应节点 $i$）是 1（表示 $i$ 被访问过），那么从 $i$ 出发能到达的节点（g[i]）中，右移一位（因为掩码对应关系变化）加入到新掩码中，表示这些节点被访问。
• ndp[S] = ... + (S & 1 ? a[i] : 0)：如果 $S$ 表示当前节点 $i$ 被访问，则加上 $a[i]$ 的吸引力。
• 最后 ans.push_back(dp[1])：dp[1] 对应掩码 00...001（只有当前节点 $i$ 被访问），这就是从 $i$ 出发的最大吸引力总和。

---

复杂度分析

• 状态数：$O(n \cdot 2^k)$
• 转移：$O(1)$
• 总复杂度：$O(n \cdot 2^k)$，在 $n=10^5, k=8$ 时可行。

---

样例验证

以样例输入：

4 4 2
3 4 5 1
1 2
2 4
1 3
3 4

输出：

13
5
6
1

• $p=1$：可达节点 {1,2,3,4}，总和 3+4+5+1=13
• $p=2$：可达节点 {2,4}，总和 4+1=5
• $p=3$：可达节点 {3,4}，总和 5+1=6
• $p=4$：可达节点 {4}，总和 1

符合输出。

---

总结

这道题利用 $k$ 很小的特点，将“可达节点集合”压缩成一个 $k$ 位掩码，通过 DP 高效求解每个起点的最大吸引力总和。
倒序 DP 使得转移更自然，避免了重复计算。
这是一个典型的状态压缩 DP 在 DAG 上的应用。