2026-04-26 某游戏厂暑期笔试复盘：三进制状态压缩 DP
题目：景点与江湖秘闻
题目大意
有 个景点、费用上限 、 个江湖秘闻。，，费用上限在 量级。
每个景点有自己的花费，以及一个秘闻集合。每个景点只能游历一次。某个秘闻收集至少两次才生效，超过两次没有额外奖励。问费用不超过 时，最多能让多少个秘闻生效。
按景点可以独立选择的模型来做：费用非负、直接累加，每个景点对集合中的每个秘闻贡献一次。
思路分析
我当时想到用三进制压状态。每一位表示一个秘闻：0 次、1 次、至少 2 次。次数超过 2 没有用，所以截到 2 即可，一共有 个状态。
费用上限很大，不能按费用开数组。用 dp[s] 记录达到状态 的最小费用，初始 dp[0]=0。逐个处理景点，每次选择不去，或付出费用后把集合内各位加 1，并截到 2。最后在费用不超过 的状态里，找三进制位为 2 最多的那个。
如果每次转移都拆开 位，就要做 次操作。 时已经有 个状态，再把除法、取模放到最内层，开销会很大。
可以把“哪些位已经是 2”提前存下来。设 saturated[s] 是状态 中已经为 2 的那些位组成的二进制集合，景点的集合是 mask。这次真正需要增加的位就是
add = mask & ~saturated[s]再预处理 weight[mask]，表示集合内所有位对应的 之和。新状态直接是
next = s + weight[add]因为只给原来为 0 或 1 的三进制位加 1，不会产生进位。已经为 2 的位又被排除了，所以这就等于逐位加一并截到 2。
这样每次转移只需要位运算和查表，不必保存 trans[mask][state] 那张大表。预处理是 ，DP 时间是 ，空间是 。
每个景点只能用一次，可以按状态编号倒序更新同一个 dp 数组：新状态不会比原状态小，倒序能防止本轮刚更新出的更大状态再次使用同一景点。如果新旧状态相等，非负费用也不会让最小费用变得更小。
参考代码
费用用 long long，只保留不超过预算的转移。下面是优化后的核心函数。
#include <bits/stdc++.h>
using namespace std;
// 每个元素为 {费用, 秘闻集合的二进制 mask}。
// 秘闻编号已转换成 0..K-1；每景点对集合内各秘闻贡献一次。
int max_active_rumors(int K, long long W,
const vector<pair<long long, int>>& spots) {
vector<int> pow3(K + 1, 1);
for (int b = 0; b < K; ++b) pow3[b + 1] = pow3[b] * 3;
int S = pow3[K];
int M = 1 << K;
// weight[mask] = mask 中各位对应的 3^b 之和。
vector<int> weight(M, 0);
for (int mask = 1; mask < M; ++mask) {
int b = __builtin_ctz((unsigned)mask);
weight[mask] = weight[mask & (mask - 1)] + pow3[b];
}
// saturated[s]：状态 s 中三进制位为 2 的那些秘闻。
vector<int> saturated(S, 0);
for (int s = 1; s < S; ++s)
saturated[s] = (saturated[s / 3] << 1) | (s % 3 == 2);
const long long INF = (1LL << 62);
vector<long long> dp(S, INF);
dp[0] = 0;
for (auto [cost, mask] : spots) {
if (cost > W) continue;
// 选景点后状态编号只会增大；倒序更新避免重复选它。
for (int s = S - 1; s >= 0; --s) {
if (dp[s] == INF || dp[s] > W - cost) continue;
int add = mask & ~saturated[s];
int next = s + weight[add];
dp[next] = min(dp[next], dp[s] + cost);
}
}
int answer = 0;
for (int s = 0; s < S; ++s)
if (dp[s] <= W)
answer = max(answer, __builtin_popcount((unsigned)saturated[s]));
return answer;
}转移表的空间开销
另一个办法是把 trans[mask][state] 全部预处理出来，之后直接查表。但 时，这张表有 项，用 int 存约占 231MiB。只给实际出现的 mask 建表可以节省一些空间，最坏仍可能出现全部 种。
也可以只保存每个状态的三进制位，转移时遍历 mask 的置位。这样避开了反复除法和取模，但一次转移仍要遍历若干位。上面的 saturated + weight 则把这一步也变成了位运算和查表。