租用游艇
题目描述
长江游艇俱乐部在长江上设置了 \(n\) 个游艇出租站 \(1,2,\cdots,n\)。游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站 \(i\) 到游艇出租站 \(j\) 之间的租金为 \(r(i,j)\)（\(1\le i\lt j\le n\)）。试设计一个算法，计算出从游艇出租站 \(1\) 到游艇出租站 \(n\) 所需的最少租金。
输入格式
第一行中有一个正整数 \(n\)，表示有 \(n\) 个游艇出租站。接下来的 \(n-1\) 行是一个半矩阵 \(r(i,j)\)（\(1\le i<j\le n\)）。
输出格式
输出计算出的从游艇出租站 \(1\) 到游艇出租站 \(n\) 所需的最少租金。
样例 #1
样例输入 #1
3
5 15
7
样例输出 #1
12
提示
\(n\le 200\)，保证计算过程中任何时刻数值都不超过 \(10^6\)。
解析
\(一道DP题\)
样例解析
3
5 15
7
中，显然5和15是中转站1到2和3的价钱，而7是2到3的价钱。我们可以用a数组来存，\(a[i][j]\)表示\(i\)到\(j\)的价钱。（左边表示出发站，右边表示到达站）
| 中转站1 | 中转站2 | 中转站3 | |
|---|---|---|---|
| 中转站1 | 0 | 5 | 15 |
| 中转站2 | 0 | 0 | 7 |
| 中转站3 | 0 | 0 | 0 |
我们可以用\(dp\)数组来记录这个中转站到n号中转站的最小价钱，\(dp[i]\)表示中转站\(i\)到中转站\(n\)的最小价钱
| 中转站1 | 中转站1 | 中转站1 | |
|---|---|---|---|
| 最小价钱 | 12 | 7 | 0 |
我们要用\(i\)把\(n\)上流的中转站从大到小跑一遍。我们先记录中转站2到中转站3的最小价钱，我们要用\(j\)跑一遍中转站2下流的所有中转站，记录\(a[i][j]+dp[j]\)的最小价钱,记录到\(dp[i]\)里面。
状态
\(f[i][j]\)表示从\(i\)站到\(j\)站的最少租金
状态转移方程
\[f[i][j] = min(f[i][j],f[i][k] + f[k+1][j])
\]
\((i \leq k \leq j)\)
初始条件
- \(f[i][j]=a[i][j];\)
- 其余\(f[i][j]\)为无穷大
代码
法1
#include <bits/stdc++.h>
using namespace std;
int a[201][201],dp[201][201];
int main()
{
int n;
cin >> n;
for(int i=1;i<n;i++)
{
for(int j=i+1;j<=n;j++)
{
cin >> a[i][j];
dp[i][j]=a[i][j];
//建立一个初始最小租金
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(dp[i][j]==0)
{
dp[i][j]=0xffffff;
/*如果我们没有这两点最初的最小租金，那么就将其赋予一个很大的量
这样可以使后面比较时不会出错*/
}
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
for(int k=1;k<=n;k++)
{
if(dp[i][k]+dp[k][j]<dp[i][j])
{
dp[i][j]=dp[i][k]+dp[k][j];
}
}
}
}
cout << dp[1][n];
return 0;
}
法2
#include <bits/stdc++.h>
using namespace std;
int a[201][201],n,dp[201];
int main()
{
cin >> n;
for(int i=1;i<n;i++)
{
for(int j=i+1;j<=n;j++)
{
cin>>a[i][j];
}
dp[i]=1e9;//初始化数组dp
}
for(int i=n-1;i>=1;i--)//跑n上流的中转站
{
for(int j=i+1;j<=n;j++)//跑i下流的所有中转站
{
dp[i]=min(dp[i],a[i][j]+dp[j]);//记录
}
}
cout<<dp[1];
return 0;
}