题解 | #最强碰撞#

最强碰撞

https://www.nowcoder.com/practice/9796395a28494748b08840170af39216

题目链接

PEEK145 最强碰撞

题目描述

火星科研团队发现了 $N$ 颗性质各异的原子，编号依次为 $0, 1, \dots, N-1$ 。他们可以任取其中两颗原子进行碰撞，碰撞后，其中一颗原子会消失并从系统中移除，同时产生一定的能量。这个过程会一直持续，直到只剩下一颗原子为止。

研究人员已经提前测得了任意两颗原子 $i$ 和 $j$ 发生碰撞，如果原子 $j$ 消失，能够产生的能量为 $E_{ij}$ 。为了获得尽可能多的总能量，他们可以自由决定碰撞的顺序，以及每次碰撞中哪颗原子消失。你需要帮助研究人员设计碰撞顺序，使得所有 $N-1$ 次碰撞产生的能量之和最大。

解题思路

这是一个寻找最优决策序列以获取最大收益的问题。观察到原子数量 $N$ 的范围非常小（通常 $N \le 16$ ），这是使用状态压缩动态规划（State Compression DP）的典型信号。

我们的目标是记录一系列碰撞后获得的最大能量。一个碰撞过程可以用当前哪些原子“存活”或“消失”来描述。因此，我们可以用一个整数的二进制位来表示所有原子的状态集合。

状态定义

我们定义一个 DP 数组 $dp[S]$ ，其中 $S$ 是一个 $N$ 位的二进制数（位掩码），它的第 $i$ 位为 $1$ 表示第 $i$ 颗原子已经消失，为 $0$ 则表示第 $i$ 颗原子仍然存在。

$dp[S]$ 的值就表示：在 $S$ 所描述的原子消失集合下，可以获得的最大总能量。

状态转移

我们的目标是计算出所有可能的 $dp[S]$ 。我们可以通过枚举当前状态，然后考虑下一步可能发生的碰撞来更新后续状态的值。这是一种“推”的 DP 思路。

假设我们当前处于状态 $S$ ，这意味着集合 $S$ 中的原子已经消失了。此时，我们可以从仍然存在的原子中，任意挑选两颗，比如 $i$ 和 $j$ （即 $S$ 的第 $i$ 位和第 $j$ 位都为 $0$ ），让它们进行碰撞。

如果让原子 $j$ 消失：
- 系统获得能量 $E_{ij}$ 。
- 状态将从 $S$ 转移到一个新的状态 $S'$ ，其中原子 $j$ 也消失了。这个新状态 $S'$ 的位掩码就是 $S | (1 << j)$ 。
- 我们用当前的总能量 $dp[S] + E_{ij}$ 来更新新状态的 DP 值。即： $dp[S \text{ | } (1 \ll j)] = \max(dp[S \text{ | } (1 \ll j)], dp[S] + E_{ij})$
同理，如果让原子 $i$ 消失，状态会转移到 $S | (1 << i)$ ，并获得能量 $E_{ji}$ 。

我们可以遍历所有当前状态 $S$ ，再遍历所有可能的碰撞组合 $(i, j)$ ，用上述方法更新所有可达的未来状态。

初始状态

最开始时，没有任何原子消失，所以初始状态是 $S=0$ 。此时的总能量为 $0$ ，即 $dp[0] = 0$ 。

最终答案

整个过程会进行 $N-1$ 次碰撞，最终会留下 $1$ 颗原子，也就是有 $N-1$ 颗原子消失。
因此，最终的答案就是所有包含了 $N-1$ 个消失原子（即二进制表示中有 $N-1$ 个 $1$ ）的状态 $S$ 中， $dp[S]$ 的最大值。

整个算法的流程如下：

初始化 $dp$ 数组，设置 $dp[0] = 0$ ，其余为 $0$ 。
遍历所有状态 $S$ 从 $0$ 到 $(1 \ll N) - 1$ 。
对于每个状态 $S$ ，遍历所有可能的原子对 $(i, j)$ 。
如果原子 $i$ 和 $j$ 在状态 $S$ 中都还存在，则模拟它们碰撞并分别计算两种消失情况（ $i$ 消失或 $j$ 消失）带来的能量增益，并更新对应的新状态的 $dp$ 值。
所有状态更新完毕后，遍历所有满足 $popcount(S) == N - 1$ 的状态 $S$ ，找出其中最大的 $dp[S]$ 值即为答案。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    while (cin >> n && n != 0) {
        vector<vector<int>> energy(n, vector<int>(n));
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                cin >> energy[i][j];
            }
        }

        vector<long long> dp(1 << n, 0);

        for (int s = 0; s < (1 << n); ++s) {
            for (int i = 0; i < n; ++i) {
                // 检查原子 i 是否存在
                if (!((s >> i) & 1)) {
                    for (int j = 0; j < n; ++j) {
                        // 检查原子 j 是否存在，且不与 i 相同
                        if (i != j && !((s >> j) & 1)) {
                            // i 与 j 碰撞，j 消失
                            int next_s = s | (1 << j);
                            dp[next_s] = max(dp[next_s], dp[s] + energy[i][j]);
                        }
                    }
                }
            }
        }

        long long max_energy = 0;
        for (int s = 0; s < (1 << n); ++s) {
            int set_bits = 0;
            for (int i = 0; i < n; ++i) {
                if ((s >> i) & 1) {
                    set_bits++;
                }
            }
            if (set_bits == n - 1) {
                max_energy = max(max_energy, dp[s]);
            }
        }
        cout << max_energy << endl;
    }
    return 0;
}

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n;
        while ((n = sc.nextInt()) != 0) {
            int[][] energy = new int[n][n];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    energy[i][j] = sc.nextInt();
                }
            }

            long[] dp = new long[1 << n];
            Arrays.fill(dp, 0);

            for (int s = 0; s < (1 << n); s++) {
                for (int i = 0; i < n; i++) {
                    // 检查原子 i 是否存在
                    if ((s & (1 << i)) == 0) {
                        for (int j = 0; j < n; j++) {
                            // 检查原子 j 是否存在，且不与 i 相同
                            if (i != j && (s & (1 << j)) == 0) {
                                // i 与 j 碰撞，j 消失
                                int nextS = s | (1 << j);
                                dp[nextS] = Math.max(dp[nextS], dp[s] + energy[i][j]);
                            }
                        }
                    }
                }
            }

            long maxEnergy = 0;
            for (int s = 0; s < (1 << n); s++) {
                if (Integer.bitCount(s) == n - 1) {
                    maxEnergy = Math.max(maxEnergy, dp[s]);
                }
            }
            System.out.println(maxEnergy);
        }
    }
}

import sys

for line in sys.stdin:
    n = int(line)
    if n == 0:
        break
    
    energy = []
    for _ in range(n):
        energy.append(list(map(int, sys.stdin.readline().split())))
        
    dp = [0] * (1 << n)
    
    for s in range(1 << n):
        for i in range(n):
            # 检查原子 i 是否存在
            if not ((s >> i) & 1):
                for j in range(n):
                    # 检查原子 j 是否存在，且不与 i 相同
                    if i != j and not ((s >> j) & 1):
                        # i 与 j 碰撞，j 消失
                        next_s = s | (1 << j)
                        dp[next_s] = max(dp[next_s], dp[s] + energy[i][j])
                        
    max_energy = 0
    for s in range(1 << n):
        if bin(s).count('1') == n - 1:
            max_energy = max(max_energy, dp[s])
            
    print(max_energy)

算法及复杂度

算法：状态压缩动态规划
时间复杂度：状态总数为 $2^N$ 。对于每个状态，我们需要两层循环来枚举所有可能的碰撞原子对 $(i, j)$ ，这需要 $\mathcal{O}(N^2)$ 的时间。因此，总时间复杂度为 $\mathcal{O}(2^N \cdot N^2)$ 。
空间复杂度：我们需要一个 $dp$ 数组来存储所有状态的能量值，其大小为 $2^N$ 。因此，空间复杂度为 $\mathcal{O}(2^N)$ 。