租用游艇

題目描述

長江游艇俱樂部在長江上設置了 \(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\)的價錢。（左邊表示出發站，右邊表示到達站）

我們可以用\(dp\)數組來記錄這個中轉站到n號中轉站的最小價錢，\(dp[i]\)表示中轉站\(i\)到中轉站\(n\)的最小價錢

我們要用\(i\)把\(n\)上流的中轉站從大到小跑一遍。我們先記錄中轉站2到中轉站3的最小價錢，我們要用\(j\)跑一遍中轉站2下流的所有中轉站，記錄\(a[i][j]+dp[j]\)的最小價錢,記錄到\(dp[i]\)裡面。

狀態

\(f[i][j]\)表示從\(i\)站到\(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;
}

本文來自小默的博客，轉載請註明原文鏈接：https://www.cnblogs.com/momotrace/p/p1359.html