题意简述

求有向无环图中一个点能到的所有点的权值和，其中这个有向无环图满足连接的任意两点编号差的绝对值不超过 $k$。

解题

我们观察到这道题两个特点。

• $k \le 8$。
• 连续两个点“可以到的”点的集合差距很小。

我们考虑用这个特点解题。定义 $dp_{i,S}$ 表示考虑第 $i$ 个点，“假设 $i$ 点能到的点集为 $S$”能到的点权和。

首先，我们判断 $S$ 最末位是否为 $1$，如果是就加入 $f_i$，否则不加。然后我们右移 $S$ 得到一个新数，此时这个数就可以作为 $i+1$ 的一个状态了。如果 $i$ 可以直接到 $i+1$，那将 $S$ 或上 $i+1$ 能到的（题目给出）就可以得到一个可以转移的状态，否则不或即可。

然后答案显然就是 $dp_{i,s_i}$，其中 $s_i$ 为 $i$ 实际的可达集合。

代码

实现细节可以看注释。

#include<iostream>
using namespace std;
using ll = long long;
ll n, m, k, f[521], g[521], S[100005], val[100005], x, y, ans[100005];
int main() {
	cin >> n >> m >> k;
	for(int i = 1; i <= n; i++) {
		cin >> val[i];
		S[i] = 1; // 可达集合包含自己
	}
	for(int i = 1; i <= m; i++) {
		cin >> x >> y;
		S[x] |= (1 << y - x); // 计算可达集合
	}
	for(int i = n; i >= 1; i--) {
		for(ll s = 0; s < (1 << k + 1); s++) {
			f[s] = (s & 1) * val[i]; // 是否有 i
			f[s] += ((s & 2) == 2 ? g[(s >> 1) | S[i + 1]] : g[s >> 1]); // 是否或上 i+1 的实际可达集合
		}
		ans[i] = f[S[i]]; // 得到答案
		for(int s = 0; s < (1 << k + 1); s++) g[s] = f[s], f[s] = 0; // 滚动数组优化空间
	}
	for(int i = 1; i <= n; i++) cout << ans[i] << endl;
	return 0;
}