题解：P7751 [COCI 2013/2014 #2] PUTNIK

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

CPP

#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 们指出。

题解：P7751 [COCI 2013/2014 #2] PUTNIK

文章操作

1. 分析

2. dp 数组定义

3. 细节

4. code

相关推荐

评论

题解：P7751 [COCI 2013/2014 #2] PUTNIK