题解 | dd爱探险 #

$[状态压缩DP]$

$DP$ 方程的建立： $dp[state][start][type]$ ：

$state$ 表示的状态，即从 $start$ 出发，已经走了所有的点用二进制存储，这个二进制数就是 $state$ 。例如如果 $state=11$ ， $11$ 的二进制为 $1011$ ，那么从 $start$ 出发经过的所有点有 $0,1,3$ .
$start$ 表示起点
$type$ 包括 $0,1,2,3$ 。因为题目说有重力加速与反重力加速，那么可以有四种：从 $start$ 出发，即没有使用重力加速也没有使用反重力加速，此时 $type$ 为 $0$ ；使用重力加速但没有使用反重力加速，此时 $type$ 为 $1$ ；没有使用重力加速但使用反重力加速，此时 $type$ 为 $3$ ；既没有使用重力加速也没有使用反重力加速，此时 $type$ 为 $3$ ；

初始化：

很显然我们得把 $DP$ 都给初始化无穷大，因为我们求的是最短距离。但是对于起点，其距离得初始化为 $0$

memset(dp, 0x3f3f3f3f, sizeof(dp));
for(int i = 0; i < n; i ++) dp[1 << i][i][0] = 0;

动态转移方程：

对于 $dp[i][j][0]$ ，既没有使用重力加速度也没有使用反重力加速度：那么它从另外一个点 $k$ 转移而来时，就是 $dp[i][j][0]=min(dp[i][j][0],dp[i\verb|^| (1<<j)][k][0]+dist[k][j])$ 。 $i\verb|^| (1<<j)$ 表示的是，除去 $j$ 的这个点。

对于 $dp[i][j][1]$ ，既没有使用重力加速度也没有使用反重力加速度：首先是在已经使用了重力加速度之后的转移： $dp[i][j][1]=min(dp[i][j][1],dp[i\verb|^|(1<<j)][k][1]+dist[k][j])$ ；然后是在 $k\rightarrow j$ 这里使用重力加速度： $dp[i][j][1]=min(dp[i][j][1],dp[i^\verb|^|(1<<j)][k][0])$

同理：

对于 $dp[i][j][2]$ ，有 $dp[i][j][2]=min(dp[i][j][2],dp[i\verb|^|(1<<j)][k][2]+dist[k][j])$ 和 $dp[i][j][2]=min(dp[i][j][2],dp[i\verb|^|(1<<j)][k][0]+2\times dist[k][j])$

对于 $dp[i][j][3]$ ，有 $dist[i][j][3]=min(dp[i][j][3],dp[i\verb|^|(1<<j)][j][3]+dist[k][j])$ 和 $dp[i][j][3]=min(dp[i][j][3],dp[i\verb|^|(1<<j)][k][1]+2\times dist[k][j])$ 和 $dp[i][j][3]=min(dp[i][j][3],dp[i\verb|^|(1<<j)][k][2])$

求解最后的答案：从任意一点出发，经过所有点刚好一次的最短总距离：

即从每一点出发，求 $dp[(1<<n)-1][start][3]$ 的最小值

总代码：

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;

const int N = 17;
int n, dist[N][N];
int dp[1 << N][N][4];
signed main(){
    HelloWorld;
    
    cin >> n;
    for(int i = 0; i < n; i ++){
        for(int j = 0; j < n; j ++) cin >> dist[i][j];
    }
    memset(dp, 0x3f3f3f3f, sizeof(dp));
    for(int i = 0; i < n; i ++) dp[1 << i][i][0] = 0;

    for(int i = 0; i < (1 << n); i ++){
        for(int j = 0; j < n; j ++){
            if((i >> j) & 1){
                for(int k = 0; k < n; k ++){
                    if((j != k) && ((i >> k) & 1)){
                        dp[i][j][0] = min(dp[i][j][0], dp[i ^ (1 << j)][k][0] + dist[k][j]);
                        dp[i][j][1] = min(dp[i][j][1], dp[i ^ (1 << j)][k][1] + dist[k][j]);
                        dp[i][j][1] = min(dp[i][j][1], dp[i ^ (1 << j)][k][0]);
                        dp[i][j][2] = min(dp[i][j][2], dp[i ^ (1 << j)][k][2] + dist[k][j]);
                        dp[i][j][2] = min(dp[i][j][2], dp[i ^ (1 << j)][k][0] + 2 * dist[k][j]);
                        dp[i][j][3] = min(dp[i][j][3], dp[i ^ (1 << j)][k][3] + dist[k][j]);
                        dp[i][j][3] = min(dp[i][j][3], dp[i ^ (1 << j)][k][2]);
                        dp[i][j][3] = min(dp[i][j][3], dp[i ^ (1 << j)][k][1] + 2 * dist[k][j]);
                    }
                }
            }
        }
    }
    int ans = 1e18;
    for(int i = 0; i < n; i ++) ans = min(ans, dp[(1 << n) - 1][i][3]);
    cout << ans << endl;
    return 0;
}