首页 > 试题广场 >

dd爱探险

[编程题]dd爱探险
  • 热度指数：850 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
星际中有个空间站，任意两个空间站间可以相互跳跃，由空间站跳跃到空间站所需要的代价为,注意不保证，可以任意选择出发的空间站，并通过恰好次跳跃把所有空间站跳完，并且必须选择次跳跃，其中一次跳跃中进行重力加速，另一次跳跃中进行反重力加速，重力加速会导致当前跳跃代价变为，反重力加速会导致当前跳跃代价翻倍(乘)，问跳完所有空间站所需要最小代价

输入描述:
第一行一个数n(3≤n≤16)
接下来n行每行n个数，第x行第y个数表示p[x][y](0≤p[x][y]≤100000)


输出描述:
一个数,表示最小代价
示例1

输入

3
0 2 1
2 0 1
3 1 0

输出

2

说明

1->2重力加速
2->3反重力加速
代价0+1*2=2
算法知识视频讲解
添加回答
C++
kilomatutinal头像 kilomatutinal

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

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

这道题可以使用状态压缩动态规划（状压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;
}
/*
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣤⣤⡀⣀⣠⣤⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣀⡀⢀⣴⣾⣷⣶⣾⣿⣿⣿⣿⣿⣿⣿⣿⣷⣾⣿⣷⣦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣾⣿⣿⣿⣿⣿⣿⣿⠿⠛⠛⠉⠉⠉⠉⠉⠉⠛⠻⠿⣿⣿⣿⣿⣿⣶⣤⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⢠⣾⣿⣿⣿⡿⠿⠛⠉⠉⠉⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠙⠿⣿⣿⣿⣷⣄⡀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⣀⣿⣿⣿⠟⠁⠀⠀⠀⠀⠀⠀⠀⣰⡆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⠿⣿⣿⣿⡄⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⣠⣾⣿⣿⠟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣶⣄⠀⠀⠀⠀⠀⢀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⣻⣿⣿⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⢹⣿⡿⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⣿⠁⠈⢢⡀⠀⠀⠀⢸⡇⢀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠻⣿⡟⠒⢦⡀⠀⠀⠀
⠀⠀⣠⣤⣤⣼⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠸⡇⠀⠀⠀⠉⢢⣄⠀⠀⢿⠊⠳⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⣷⡄⠀⢷⠀⠀⠀
⠀⢰⠇⠀⣰⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡇⠀⠀⠀⠀⡌⣹⠗⠦⣬⣇⠀⠉⢢⡀⠀⠀⠀⠀⠀⠀⠀⠀⠘⣿⡀⢸⡄⠀⠀
⠀⡟⠀⣼⣯⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⣆⢹⡀⠀⠀⠀⠉⠁⠀⠀⢀⣀⡁⠀⠀⠉⠳⢴⡆⠀⠀⠀⠀⠀⠀⢹⣧⠈⡇⠀⠀
⠀⡇⠀⠀⢻⣦⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣾⠻⠉⠛⠂⠀⠀⠀⠀⠀⠀⠻⠿⣿⣿⣿⣶⣦⡀⠛⣇⠀⠀⠀⠀⠀⣈⣿⠀⡇⠀⠀
⢸⡇⠀⠀⢠⣿⣷⣦⣀⡸⣷⣦⣶⡂⠉⠉⠉⢁⣤⣶⡶⠀⠀⠀⣀⣀⡴⠀⠀⠀⠀⠀⠀⠈⠉⠉⠁⠀⡟⢀⣴⣟⣰⣾⣿⣏⣠⠇⠀⠀
⠈⡇⠀⠀⢸⣿⠁⠉⣿⠛⠛⠃⡇⠀⠀⢠⣶⣿⡿⠛⠁⠀⠀⠉⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠼⢿⠟⠿⢿⡏⠀⠘⣿⡀⠀⠀⠀
⠀⢷⣀⣀⣿⠇⠀⠀⢿⡇⠀⢀⢱⡀⠀⠛⠛⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣼⠀⠀⢸⠇⠀⠀⢹⣿⣄⠀⠀
⠀⠀⣉⣿⡏⠀⠀⠀⠀⠀⠀⢸⣇⣳⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡰⣿⠃⠀⠀⠀⠀⠀⠀⣿⠈⢧⠀
⠀⠘⣿⣿⠁⠀⠀⠀⠀⠀⠀⠘⣿⡛⣶⠀⠀⣠⠔⠒⠛⠒⠦⡀⠀⠀⠀⠀⣠⡤⠶⠤⢤⣀⠀⠀⠀⢀⣏⡄⠀⠀⠀⠀⠀⡀⣿⡆⠈⣧
⣠⡾⠛⣿⣿⣧⠀⠀⠀⠀⢸⣿⠾⢿⡿⠀⣰⠃⠀⠀⠀⠀⠀⢹⡄⠀⠀⡼⠁⠀⠀⠀⠀⠈⠙⣦⠀⢸⣿⡇⣾⣣⡀⠀⢰⣿⣿⣿⣤⠾
⡟⠀⠀⠻⣿⡟⢷⡄⣤⡀⠈⣿⡀⣸⠇⠀⠏⠀⠀⠀⠀⠀⠀⠀⡇⠀⠀⡇⢀⡀⠀⠀⠀⠀⢀⡟⠀⠀⠋⣿⣿⣿⡇⣠⣿⠿⠛⢷⡀⠀
⠀⠀⠀⠀⣿⣇⣨⣿⣿⣿⣦⣽⣷⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠁⠀⠀⠃⠀⠙⠢⠤⠤⠴⢾⠀⠀⠀⠀⢸⣷⣿⣿⠟⠁⠀⠀⠈⣧⠀
⠀⠀⠀⠀⠈⠉⠉⠁⠈⠉⠈⢉⣿⡁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠀⠀⠀⠀⢸⡇⠀⠀⠀⠀⠀⠀⠀⣿⠀
*/
发表于 2026-01-24 11:35:43 回复(0)
周康禧头像 周康禧
因为n很小，只有最多16，所以考虑状压dp，代表当前已经访问了mask中二进制已经为1的空间站并且目前在第k个空间站的最小代价，分别代表当前已经访问了mask中二进制已经为1的空间站并且目前在第k个空间站的过程中最大的代价跟最小的代价，因为我们要将一次代价变成0，一次代价翻倍，那么就相当于把最大的变成0，把最小的多算一次，转移的时候分类讨论一下
时间复杂度是
#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
using ld = long double;
using PII=pair<ll,ll>;
using PIII=pair<int,pair<int,int>>;
const ld ESP = 1e-10;
const ld PI = acosl(-1);
const int N=2e5+10;
const int M=1e6+10;
const int mod = 1000000007;
// const int mod = 998244353;
//随机化
random_device rd;
mt19937 gen(rd());
uniform_int_distribution<> Tp(1, 100);
// cout<<fixed<<setprecision(10);


void solve(){
    int n;
    cin>>n;
    vector<vector<int>> dp(1<<n,vector<int>(n+1,0));
    vector<vector<int>> dmx(1<<n,vector<int>(n+1,-1));
    vector<vector<int>> dmi(1<<n,vector<int>(n+1,1e9));
    int c[n][n];
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>c[i][j];
        }
    }
    int mask=1<<n;
    for(int i=0;i<mask;i++){
        int cnt=__builtin_popcount(i);
        if(cnt>=4){
            for(int j=0;j<n;j++){
                if(i>>j&1){
                    int res=1e9;
                    int mxf=1e9,mif=0;
                    for(int k=0;k<n;k++){
                        if((i>>k&1)&&j!=k){
                            if(c[k][j]>dmx[i^(1<<j)][k]){
                                if(res>dp[i^(1<<j)][k]+dmx[i^(1<<j)][k]){
                                    res=dp[i^(1<<j)][k]+dmx[i^(1<<j)][k];
                                    mxf=c[k][j];
                                    mif=dmi[i^(1<<j)][k];
                                }
                            }
                            else if(c[k][j]<dmi[i^(1<<j)][k]){
                                if(res>dp[i^(1<<j)][k]-dmi[i^(1<<j)][k]+2*c[k][j]){
                                    res=dp[i^(1<<j)][k]-dmi[i^(1<<j)][k]+2*c[k][j];
                                    mxf=dmx[i^(1<<j)][k];
                                    mif=c[k][j];
                                }
                            }else{
                                if(res>dp[i^(1<<j)][k]+c[k][j]){
                                    res=dp[i^(1<<j)][k]+c[k][j];
                                    mxf=dmx[i^(1<<j)][k];
                                    mif=dmi[i^(1<<j)][k];
                                }
                            }
                        }
                    }
                    dp[i][j]=res;
                    dmx[i][j]=mxf;
                    dmi[i][j]=mif;
                }
            }
        }else{
            if(cnt==2){
                for(int j=0;j<n;j++){
                    if(i>>j&1){
                        for(int k=0;k<n;k++){
                            if((i>>k&1)&&j!=k){
                                dmx[i][k]=c[j][k];dmi[i][k]=c[j][k];
                                dmx[i][j]=c[k][j];dmi[i][j]=c[k][j];
                            }
                        }
                    }
                }
            }else if(cnt==3){
                for(int j=0;j<n;j++){
                    if(i>>j&1){
                        for(int k=0;k<n;k++){
                            if((i>>k&1)&&j!=k){
                                dmx[i][j]=max(dmx[i^(1<<j)][k],c[k][j]);
                                dmi[i][j]=min(dmi[i^(1<<j)][k],c[k][j]);
                            }
                        }
                        dp[i][j]=2*dmi[i][j];
                    }
                }
            }
        }
    }
    int ans=1e9;
    for(int i=0;i<n;i++){
        ans=min(dp[mask-1][i],ans);
    }cout<<ans;
}  
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int _=1;
    // cin>>_;
    while(_--){
        solve();
    }
    return 0;
}


发表于 2026-01-24 15:05:22 回复(0)
C++
Turgen头像 Turgen
有没有人知道为什么这题不能记忆化搜索
发表于 2026-01-25 01:41:05 回复(0)
C++
驴主头像 驴主
又是 Python 转 C++ 的一天。 
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <climits>
using namespace std;

const long long INF = LLONG_MAX / 2;
int n;
vector<vector<int>> g;
long long memo[1 << 16][17][2][2];

long long f(int s, int last, bool ga, bool aga) {
    // 使用缓存
    if (memo[s][last][ga][aga] != -1) {
        return memo[s][last][ga][aga];
    }
    
    if (s == 0) {
        // 所有节点都已访问
        if (ga || aga) {
            return INF;
        }
        return 0;
    }
    
    long long ans = INF;
    for (int i = 0; i < n; i++) {
        if (!(s & (1 << i))) {
            continue;
        }
        
        int d = g[i][last];
        int t = s ^ (1 << i);
        long long x = f(t, i, ga, aga) + d;
        
        if (last == n) {
            ans = min(ans, x);
            continue;
        }
        
        if (ga) {
            x = min(x, f(t, i, false, aga));
        }
        if (aga) {
            x = min(x, f(t, i, ga, false) + 2 * d);
        }
        ans = min(ans, x);
    }
    
    memo[s][last][ga][aga] = ans;
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n;
    g.resize(n + 1, vector<int>(n + 1, 0));
    
    // 读取邻接矩阵
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> g[i][j];
        }
        g[i][n] = 0;  // 虚拟终点的边权为0
    }
    
    // 初始化备忘录
    memset(memo, -1, sizeof(memo));
    
    int s = (1 << n) - 1;
    long long result = f(s, n, true, true);
    cout << result << endl;
    
    return 0;
}


发表于 2026-01-24 22:01:08 回复(0)
_changbin头像 _changbin 
#include<bits/stdc++.h>
using namespace std;
#define int long long
int p[20][20];
int dp[1<<16][16][2][2];//mask,u,g,a
const int INF = 0x3f3f3f3f3f3f3f3f;
void solve(){
    int n;cin>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>p[i][j];
        }
    }
    memset(dp,0x3f,sizeof(dp));
    for(int i=0;i<n;i++) dp[1<<i][i][0][0]=0;
    for(int mask=1;mask<(1<<n);mask++){
        for(int u=0;u<n;u++){
            if(!(mask&(1<<u))) continue;
            for(int g=0;g<=1;g++){
                for(int a=0;a<=1;a++){
                    if(dp[mask][u][g][a]==INF) continue;
                    for(int v=0;v<n;v++){
                        if(mask&(1<<v)) continue;
                        int newmask=mask|(1<<v);
                        dp[newmask][v][g][a]=min(dp[newmask][v][g][a],dp[mask][u][g][a]+p[u][v]);
                        if(!g) dp[newmask][v][1][a]=min(dp[newmask][v][1][a],dp[mask][u][g][a]);
                        if(!a) dp[newmask][v][g][1]=min(dp[newmask][v][g][1],dp[mask][u][g][a]+2*p[u][v]);
                }
                }
            }
        }
    }
    int ans=INF;
    for(int i=0;i<n;i++) ans=min(ans,dp[(1<<n)-1][i][1][1]);
    cout<<ans;
}
signed main(){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t=1;
    // cin>>t;
    while(t--){
        solve();
    }return 0;
}

发表于 2026-01-24 19:38:09 回复(0)
C++
Reisentyan头像 Reisentyan
我们将使用拉马努金瞪眼法解决这一题
注意到，这题使用的是 SOS DP，其状态转移方程如下：
		dp[sta][i][0] = min(dp[sta ^ (1 << i)][jp][0] + p[jp][i], dp[sta][i][0]);

		dp[sta][i][1] = min(dp[sta ^ (1 << i)][jp][0], dp[sta][i][1]);
		dp[sta][i][1] = min(dp[sta ^ (1 << i)][jp][1] + p[jp][i], dp[sta][i][1]);

		dp[sta][i][2] = min(dp[sta ^ (1 << i)][jp][0] + p[jp][i] * 2, dp[sta][i][2]);
		dp[sta][i][2] = min(dp[sta ^ (1 << i)][jp][2] + p[jp][i], dp[sta][i][2]);

		dp[sta][i][3] = min(dp[sta ^ (1 << i)][jp][1] + p[jp][i] * 2, dp[sta][i][3]);
		dp[sta][i][3] = min(dp[sta ^ (1 << i)][jp][2], dp[sta][i][3]);
		dp[sta][i][3] = min(dp[sta ^ (1 << i)][jp][3] + p[jp][i], dp[sta][i][3]);
做完了。
因为是 dp，所以请大胆的写下去吧

发表于 2026-01-24 19:23:03 回复(1)
提交观点

问题信息

难度：
6条回答 10浏览

热门推荐

相关试题

dd爱探险

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号