（题解建议配合代码一起食用喵~）

不会这道题吗？让猫猫来帮帮你吧！

这道题可以使用状态压缩动态规划（状压DP）解决喵！

我们先看看怎么表示状态的喵~

这道题我定义了dp数组dp[i][j][k]喵！

  • i：二进制掩码（其实就是表示状态），表示猫猫已经访问了哪些空间站，比如如i=5（二进制101）代表访问了第0和第2个空间站。
  • j：表示现在猫猫站在哪一个空间站。
  • k：加速状态：
  • k=0：猫猫没有加速过。
  • k=1：已使用重力加速（一次跳跃代价变为0）。
  • k=2：已使用反重力加速（一次跳跃代价翻倍）。
  • k=3：两种加速均已使用。
  • dp[i][j][k]的值表示在状态（i，j，k）花费的最小动能。

既然是dp那肯定有状态转移公式的喵！

dp[i][j][k]肯定是由上一个状态转移(dp[ii][jj][kk])来的喵！

首先 i 中，j 的状态会消失。因为 j 是现在所在的空间站位置。所以ii就等于i - ( 1 << j )表示未包含 j 的状态。

因为其他任何空间站都有可能跳到 j 空间站，所以 jj 我们要从1到n进行遍历一遍。（注意jj一定要在ii的状态内，猫猫总不可能还没有到那里就可以从jj开始跳吧）

而对于kk而言

dp[i][j][0~3]=min(dp[i][j][0~3],dp[ii][jj][0~3]+m[jj][j]);//m[jj][j]表示从jj跳到j需要花的动能
//各个状态普通跳
dp[i][j][1]=min(dp[i][j][1],dp[ii][jj][0]);//重力加速
//这次跳跃不要钱啦！
dp[i][j][2]=min(dp[i][j][2],dp[ii][jj][0]+m[k][j]*2);//反重力加速
//代价变成两倍，但有时候为了整体最优还是值得的喵！
dp[i][j][3]=min(dp[i][j][3],dp[ii][jj][1]+m[k][j]*2);//已经重力加速过了，进行一次反重力加速
dp[i][j][3]=min(dp[i][j][3],dp[ii][jj][2]);//已经反重力加速过了，进行一次重力加速

思路是不是非常简单呢？

呈上代码喵！

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

int main() {
    cin.tie(0)->sync_with_stdio(0);
    ll n;cin >> n;
    vector<vector<ll>> m(n,vector<ll>(n));
    vector<vector<vector<ll>>> dp(1<<n,vector<vector<ll>>(n,vector<ll>(4,1e9)));
  	//等同于ll dp[1<<n][n][4]且每个元素都是1e9
  	//这个三维数组最好不要直接用int dp[][][]表示在主函数内，可能会内存溢出。
  	//如果很想用可以放在全局变量里
    for(ll i=0;i<n;i++)
    {
        for(ll j=0;j<n;j++)
        {
            cin >> m[i][j];//初始化
        }
    }
  
    for(ll i=0;i<n;i++) dp[1<<i][i][0]=0;//表示一开始就在某一个空间站的情况，耗费动能肯定是0呀
    for(ll i=1;i<(1<<n);i++)//遍历所有状态
    {
        for(ll j=0;j<n;j++)//当前刚好处于j站点
        {
            if(!(i>>j&1)) continue;//如果j不在状态i中就跳过
            for(int jj=0;jj<n;jj++)//上一个点jj
            {
                if(j==jj||!(i>>jj&1)) continue;//jj不在i中或者等于j就跳过
                int ii=i-(1<<j);
                for(int l=0;l<4;l++)
                    dp[i][j][l]=min(dp[i][j][l],dp[ii][jj][l]+m[jj][j]);//各状态普通跳
                dp[i][j][1]=min(dp[i][j][1],dp[ii][jj][0]);//重力加速
                dp[i][j][2]=min(dp[i][j][2],dp[ii][jj][0]+m[jj][j]*2);//反重力加速
                dp[i][j][3]=min(dp[i][j][3],dp[ii][jj][1]+m[jj][j]*2);//已经重力加速过了
                dp[i][j][3]=min(dp[i][j][3],dp[ii][jj][2]);//已经反重力加速过了
            }
        }
    }
    ll ans=1e9;
    for(int i=0;i<n;i++)
    {
        ans=min(ans,dp[(1<<n)-1][i][3]);
    }
    cout << ans;
}
/*
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣤⣤⡀⣀⣠⣤⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣀⡀⢀⣴⣾⣷⣶⣾⣿⣿⣿⣿⣿⣿⣿⣿⣷⣾⣿⣷⣦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣾⣿⣿⣿⣿⣿⣿⣿⠿⠛⠛⠉⠉⠉⠉⠉⠉⠛⠻⠿⣿⣿⣿⣿⣿⣶⣤⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⢠⣾⣿⣿⣿⡿⠿⠛⠉⠉⠉⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠙⠿⣿⣿⣿⣷⣄⡀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⣀⣿⣿⣿⠟⠁⠀⠀⠀⠀⠀⠀⠀⣰⡆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⠿⣿⣿⣿⡄⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⣠⣾⣿⣿⠟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣶⣄⠀⠀⠀⠀⠀⢀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⣻⣿⣿⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⢹⣿⡿⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⣿⠁⠈⢢⡀⠀⠀⠀⢸⡇⢀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠻⣿⡟⠒⢦⡀⠀⠀⠀
⠀⠀⣠⣤⣤⣼⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠸⡇⠀⠀⠀⠉⢢⣄⠀⠀⢿⠊⠳⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⣷⡄⠀⢷⠀⠀⠀
⠀⢰⠇⠀⣰⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡇⠀⠀⠀⠀⡌⣹⠗⠦⣬⣇⠀⠉⢢⡀⠀⠀⠀⠀⠀⠀⠀⠀⠘⣿⡀⢸⡄⠀⠀
⠀⡟⠀⣼⣯⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⣆⢹⡀⠀⠀⠀⠉⠁⠀⠀⢀⣀⡁⠀⠀⠉⠳⢴⡆⠀⠀⠀⠀⠀⠀⢹⣧⠈⡇⠀⠀
⠀⡇⠀⠀⢻⣦⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣾⠻⠉⠛⠂⠀⠀⠀⠀⠀⠀⠻⠿⣿⣿⣿⣶⣦⡀⠛⣇⠀⠀⠀⠀⠀⣈⣿⠀⡇⠀⠀
⢸⡇⠀⠀⢠⣿⣷⣦⣀⡸⣷⣦⣶⡂⠉⠉⠉⢁⣤⣶⡶⠀⠀⠀⣀⣀⡴⠀⠀⠀⠀⠀⠀⠈⠉⠉⠁⠀⡟⢀⣴⣟⣰⣾⣿⣏⣠⠇⠀⠀
⠈⡇⠀⠀⢸⣿⠁⠉⣿⠛⠛⠃⡇⠀⠀⢠⣶⣿⡿⠛⠁⠀⠀⠉⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠼⢿⠟⠿⢿⡏⠀⠘⣿⡀⠀⠀⠀
⠀⢷⣀⣀⣿⠇⠀⠀⢿⡇⠀⢀⢱⡀⠀⠛⠛⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣼⠀⠀⢸⠇⠀⠀⢹⣿⣄⠀⠀
⠀⠀⣉⣿⡏⠀⠀⠀⠀⠀⠀⢸⣇⣳⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡰⣿⠃⠀⠀⠀⠀⠀⠀⣿⠈⢧⠀
⠀⠘⣿⣿⠁⠀⠀⠀⠀⠀⠀⠘⣿⡛⣶⠀⠀⣠⠔⠒⠛⠒⠦⡀⠀⠀⠀⠀⣠⡤⠶⠤⢤⣀⠀⠀⠀⢀⣏⡄⠀⠀⠀⠀⠀⡀⣿⡆⠈⣧
⣠⡾⠛⣿⣿⣧⠀⠀⠀⠀⢸⣿⠾⢿⡿⠀⣰⠃⠀⠀⠀⠀⠀⢹⡄⠀⠀⡼⠁⠀⠀⠀⠀⠈⠙⣦⠀⢸⣿⡇⣾⣣⡀⠀⢰⣿⣿⣿⣤⠾
⡟⠀⠀⠻⣿⡟⢷⡄⣤⡀⠈⣿⡀⣸⠇⠀⠏⠀⠀⠀⠀⠀⠀⠀⡇⠀⠀⡇⢀⡀⠀⠀⠀⠀⢀⡟⠀⠀⠋⣿⣿⣿⡇⣠⣿⠿⠛⢷⡀⠀
⠀⠀⠀⠀⣿⣇⣨⣿⣿⣿⣦⣽⣷⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠁⠀⠀⠃⠀⠙⠢⠤⠤⠴⢾⠀⠀⠀⠀⢸⣷⣿⣿⠟⠁⠀⠀⠈⣧⠀
⠀⠀⠀⠀⠈⠉⠉⠁⠈⠉⠈⢉⣿⡁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠀⠀⠀⠀⢸⡇⠀⠀⠀⠀⠀⠀⠀⣿⠀
*/