如果你 WA #8 ，第三行输出 6 正确答案 5

如这个记录：https://www.luogu.com.cn/record/81573625

错误写法：

CPP

dp[0] = 0;
for (int i = 1; i < 1 << n; ++i) {
    int fix = __builtin_ctz(i) + 1;
    dp[i] = min(dp[i], dp[i ^ (1 << (fix - 1))] + 1);
    for (int j = 1; j <= n; ++j) {
        if (j == fix || (i | g[fix][j]) != i) {
            continue;
        }
        dp[i] = min(dp[i], dp[i ^ g[fix][j]] + 1);
    }
}
cout << dp[(1 << n) - 1] << endl;

上面代码的大意是：枚举集合

i

，找到需要经过的第一个点

fix

，然后枚举以

fix

为第一个点

j

为第二个点的抛物线，如果抛物线覆盖的点的集合是 $i$ 的子集 那么进行转移

dp_i = \min(dp_i, dp_{i - g[fix][j]} + 1)

。

实际上粗体字部分根本没必要。应该为：不管抛物线覆盖的点是否是 $i$ 的子集都进行转移 ，

dp_i = \min(dp_i, dp_{i \cap g[fix][j] + 1})

。

改后代码：

CPP

dp[0] = 0;
for (int i = 1; i < 1 << n; ++i) {
    int fix = __builtin_ctz(i) + 1;
    dp[i] = min(dp[i], dp[i ^ (1 << (fix - 1))] + 1);
    for (int j = 1; j <= n; ++j) {
        if (j == fix) {
            continue;
        }
        dp[i] = min(dp[i], dp[i ^ (i & g[fix][j])] + 1);
    }
}
cout << dp[(1 << n) - 1] << endl;

如果你 WA #8 ，第三行输出 6 正确答案 5

讨论操作

回复

相关推荐

如果你 WA #8 ，第三行输出 6 正确答案 5