租用游艇

租用游艇

题目描述

长江游艇俱乐部在长江上设置了 \(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)\)

初始条件

  1. \(f[i][j]=a[i][j];\)
  2. 其余\(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;
}

热门相关:恭喜你被逮捕了   梦回大明春   修仙界最后的单纯   法医娇宠,扑倒傲娇王爷   法医王妃不好当!