自动搬运

查看原文

来自洛谷，原作者为

	jijian #define AK return #define IOI 0

搬运于2025-08-24 22:32:46，当前版本为作者最后更新于2025-07-15 20:16:39，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

1. 分析

下面的 dalao 们都用的搜索，我发现这道题可以维护一个连续的区间，而且每次向左或向右拓展，所以考虑区间 dp，暴力枚举两端节点（实际上和 dalao 们的思路差不多）。

2. dp 数组定义

$dp[i][j]$ 表示两端城市是 $i$ 和 $j$ 时的最小飞行时间。

3. 细节

当我们遍历到左端点为 $i$，右端点为 $j$ 的时候，不难得出下一个城市是 $\max(i,j)+1$。
设下一个城市为 $k$，当 $k>n$ 时，直接 continue（因为遍历完了），否则就直接考虑把 $k$ 接到 $i$ 前面或者 $j$ 后面。
状态转移方程：
$dp[i][k]=\min(dp[i][k],dp[i][j]+t[j][k])$。
$dp[k][j]=\min(dp[k][j],dp[i][j]+t[i][k])$。

4. code

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<vector<int>> t(n+1,vector<int>(n+1));//时间
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>t[i][j];
        }
    }
    vector<vector<int>> dp(n+1,vector<int>(n+1,INT_MAX));//dp[i][j]表示两端城市是i和j时的最小飞行时间
    dp[1][1]=0;//初始化
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(dp[i][j]==INT_MAX) continue;//不可达
            int k=max(i,j)+1;//下一个城市
            if(k>n) continue;//超出城市总数
            dp[i][k]=min(dp[i][k],dp[i][j]+t[j][k]);//将k接在i左边
            dp[k][j]=min(dp[k][j],dp[i][j]+t[i][k]);//将k接在j右边
        }
    }
    int ans=INT_MAX;
    for(int i=1;i<=n;i++){
        ans=min(ans,dp[i][n]);//求出最少时间
        ans=min(ans,dp[n][i]);
    }
    cout<<ans;
    return 0;
}

时间复杂度 $O(n^2)$。
空间复杂度 $O(n^2)$。

完结撒花，若有不足，请 dalao 们指出。