题解：P7751 [COCI 2013/2014 #2] PUTNIK
cqbz_ycr
·
·
题解
1. 分析
下面的 dalao 们都用的搜索，我发现这道题可以维护一个连续的区间，而且每次向左或向右拓展，所以考虑区间 dp，暴力枚举两端节点（实际上和 dalao 们的思路差不多）。
2. dp 数组定义
---
### 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 们指出。