题目链接
P1359 租用游艇
普及
题目描述
长江游艇俱乐部在长江上设置了
n
n
n 个游艇出租站
1
,
2
,
3
,
.
.
.
,
n
1,2,3,…,n
1,2,3,…,n，游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站
i
i
i 到游艇出租站
j
j
j 之间的租金为
r
(
i
,
j
)
(
1
≤
i
≤
j
≤
n
)
r(i,j) quad (1 leq i leq j leq n)
r(i,j)(1≤i≤j≤n) 。
请计算出从 出租站
1
1
1 到 出租站
n
n
n 所需的最少租金。
输入格式
第一行中有一个正整数
n
n
n ，表示有
n
n
n 个游艇出租站。
接下来的
n
−
1
n – 1
n−1 行是一个半矩阵
r
(
i
,
j
)
(
1
≤
i
≤
j
≤
n
)
r(i,j) quad (1 leq i leq j leq n)
r(i,j)(1≤i≤j≤n)。
输入格式
输出计算出的从游艇出租站
1
1
1 到游艇出租站
n
n
n 所需的最少租金。
数据范围
n
≤
200
n≤200
n≤200，保证计算过程中任何时刻数值都不超过
1
0
6
10^6
106 。
示例1：
输入：
3
5 15
7
输出：
12
解法：贪心
我们定义邻接矩阵
g
g
g，
g
[
i
]
[
j
]
g[i][j]
g[i][j] 记录的是 出租站
i
i
i 到 出租站
j
j
j 的距离。
我们定义
f
[
i
]
f[i]
f[i] 表示从 出租站
1
1
1 到 出租站
i
i
i 所需要的最小租金。按照定义，我们最终返回的答案就是
f
[
n
]
f[n]
f[n]。
我们可以得出如下状态转移方程：
f
[
i
]
=
m
i
n
{
f
[
i
]
,
f
[
j
]
+
g
[
j
]
[
i
]
}
(
1
≤
j
f[i]=min{f[i],f[j]+g[j][i]}(1≤ji)
时间复杂度：
O
(
n
2
服务器托管网
)
O(n^2)
O(n2)
C++代码：
#include
#include
using namespace std;
const 服务器托管网int N = 210;
int g[N][N];
void solve(){
int n;
cin>>n;
for(int i = 1;i n;i++){
for(int j = i + 1;j n;j++){
cin>>g[i][j];
}
}
vectorint> f(n + 1 , 1e9);
f[1] = 0;
for(int i = 2;i n;i++){
for(int j = 1;j i;j++) f[i] = min(f[i] , f[j] + g[j][i]);
}
coutf[n]'n';
}
int main(){
solve();
return 0;
}
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
